写在前面的

一起对于简单点分治的题都是用 解决的，结果遇到点分树，哦吼，做不来了。这才打算学一下点分治，我检讨。

点分治

引入

给你 个询问，询问一个树上是否有长度为 的路径。要求在 时间复杂度内解决。

• 如果学习过 的同学，这个就是个模板。但是这里还是考虑使用点分治解决。其实这两个算法我觉得思想也是非常一致的。
• 无序列表内容
• 我们对于一个节点可以把路径分成两种
  • 经过该节点的
  • 没有经过该节点

那么我们考虑分治。选择一个节点作为根，那么路径要么以这个节点为 ，要么根本不经过它。而这个只处理以这个为 的路径。那么剩下的路径与这个节点就没有关系，就可以去除这个节点了。例如这张图，我们处理完根节点之后，就只需要处理剩下的两个子树了。

那么我们这样的复杂度为多少，我们发现如果是一条链，而且我们每次选择第一个节点，那么这个与暴力是一样的，都是 。

• 那么我们需要一个科学的方法的，选择那个根节点。根据科学的验证，取每个树的重心是最优的。因为每次取重心，那么每次的子树变为原来的 ，那么只需要 次划分，最后就可以得到答案。 每次处理答案为 ，所以复杂度为 了。

• 那么考虑如何合并两个子树。我们开一个桶 ，定义 为处理一个子树的路径长度。那么一个答案是否出现过 。然后把 加入到桶中。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f=1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
#define pii pair<int,int>
const int N = 1e8 + 10,M = 1e5 + 10;
int n,m,tmp[N],judge[N],sz[M],vis[M];
vector<pii> G[M];int que[M];
int size,maxp[M],tot,rt,dis[M],q[N],yun[M];
void getsz(int t,int fat) {
    sz[t] = 1;maxp[t] = 0;
    for(auto e : G[t]) {
        int j = e.first;
        if(j == fat || vis[j]) continue;
        getsz(j,t);sz[t] += sz[j];
        maxp[t] = max(sz[j],maxp[t]);
    }
    maxp[t] = max(maxp[t],tot - sz[t]);
    if(maxp[t] < maxp[rt]) rt = t;
}
void getdis(int t,int fat) {
    tmp[++tmp[0]] = dis[t];
    for(auto e : G[t]) {
        int j = e.first;
        if(vis[j] || j == fat) continue;
        dis[j] = dis[t] + e.second;
        getdis(j,t);
    }
}
void clac(int t) {
    int top = 0;
    for(auto e : G[t]) {
        int j = e.first,k = e.second;
        if(vis[j]) continue; 
        tmp[0] = 0;
        dis[j] = k;
        getdis(j,k);
        for(k = tmp[0];k;k--) {
            for(int l=1;l<=m;l++){
                if(que[l]>=tmp[k]){
                    yun[l]|=judge[que[l]-tmp[k]];
                }
            }
        }
        for(k = tmp[0];k;k--) q[++top]=tmp[k],judge[tmp[k]]=1;
    }
    for(int i = top;i;i--) judge[q[i]] = 0;
}
void solve(int t) {
    vis[t] = judge[0] = 1;clac(t);
    for(auto e : G[t]) {
        int j = e.first;
        if(vis[j]) continue;tot = sz[j];
        maxp[rt = 0] = N;
        getsz(j,0);solve(rt);
    }
}
int main() {
    n = read();m = read();
    for(int i = 1,a,b,c;i < n;i++) {
        a = read();b = read();c = read();
        G[a].push_back(pii(b,c));G[b].push_back(pii(a,c));
    } 
    for(int i = 1;i <= m;i++) que[i] = read();
    maxp[rt = 0] = n;tot = n;
    getsz(1,0);solve(rt);
    for(int i = 1;i <= m;i++) {
        if(yun[i]) cout << "AYE" << endl;
        else cout << "NAY" << endl;
    }
}