点分治(淀粉质)

~{→看不见LaTex格式的Dalao们请刷新本页Thanks♪(･ω･)ﾉ←}~

(淀粉质)点分治

推荐一道模板题。

我们选择任意一个根$root​$，将树变为一棵无根树。

那么我们对于树上任意两个点之间的路径必定被转化为经过$root$的路径，或是位于$root$某一棵子树中的路径。

所以我们就能够把一条路径分到几棵子树中分治求解。点分治后，每一层分别对$n$个点处理一次，递归$k$层的复杂度为$O(kn)$。

不过当树变为一条链之后，最坏的情况是当$root$取首尾节点时，有$k=n$，时间复杂度为$O(n^2)$。

那么我们选择$root​$时应该怎么选择呢？

树的重心是个好的选择，它能使递归的层数减到最少。

我们记录每个点$i​$到根节点$root​$的距离$dis_i​$，那么从$u​$到$v​$的路径长度为$dis_u+dis_v​$。

同时设$max​$_$part[i]​$表示删除$i​$节点后，最大的子树的大小。

树的重心节点$g$一定是$max$_$part[g]=(max$_$part[i])_{min}$。

取重心也就保证了时间复杂度稳定在$O(nlogn)$左右。

是不是比原来$O(n^2)$的算法优秀了很多呢？

---

Code

#include<bits/stdc++.h>
using namespace std;
int read()
{
    int x = 0, w = 0;
    char ch = 0;
    while (!isdigit(ch)) {w |= ch == '-'; ch = getchar();}
    while (isdigit(ch)) {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
    return w ? -x : x;
}
const int N = 100010;
struct edge {
    int to, nxt, l;
} e[N];
int linkk[N], len;
void insert(int u, int v, int l)
{
    e[++len].to = v, e[len].l = l, e[len].nxt = linkk[u], linkk[u] = len;
    e[++len].to = u, e[len].l = l, e[len].nxt = linkk[v], linkk[v] = len;
}
int size[N], max_part[N], tp[N];
int tot, now_root, res[10000010], deep[N];
int n, m, q[110], c;
bool vis[N];
void getroot(int x, int fa)
{
    size[x] = 1; max_part[x] = 0;
    for (int i = linkk[x]; i; i = e[i].nxt)
    {
        int to = e[i].to;
        if (to == fa || vis[to]) continue;
        getroot(to, x);
        size[x] += size[to];
        max_part[x] = max(max_part[x], size[to]);
    }
    max_part[x] = max(max_part[x], tot - size[x]);
    if (max_part[now_root] > max_part[x]) now_root = x;
}
void getdeep(int x, int fa)
{
    tp[++c] = deep[x];
    for (int i = linkk[x]; i; i = e[i].nxt)
    {
        int to = e[i].to;
        if (to == fa || vis[to]) continue;
        deep[to] = deep[x] + e[i].l;
        getdeep(to, x);
    }
}
void calculate(int x, int dep, int del)
{
    c = 0, deep[x] = dep;
    getdeep(x, 0);
    for (int i = 1; i <= c; ++i)
        for (int j = 1; j <= c; ++j)
            res[tp[i] + tp[j]] += del;
}
void solve(int x)
{
    calculate(x, 0, 1);
    vis[x] = 1;
    for (int i = linkk[x]; i; i = e[i].nxt)
    {
        int to = e[i].to;
        if (vis[to]) continue;
        calculate(to, e[i].l, -1);
        tot = size[to], now_root = 0;
        getroot(to, 0);
        solve(to);
    }
}
int main()
{
    n = read(), m = read();
    for (int i = 1; i < n; ++i)
    {
        int u = read(), v = read(), l = read();
        insert(u, v, l);
    }
    for (int i = 1; i <= m; ++i) q[i] = read();
    now_root = 0, max_part[now_root] = tot = n;
    getroot(1, 0);
    solve(now_root);
    for (int i = 1; i <= m; ++i)
        if (res[q[i]]) puts("AYE");
        else puts("NAY");
    return 0;
}