定义
点分治，顾名思义，就是通过基于点的分治的一种算法。
通常用于处理树上问题，如树上所有路径统计。
我们设一次操作的时间复杂度为 \(O(1)\) ，那么一次点分治复杂度为 \(O(n \log n)\) 。
具体流程
操作->分治->操作……（不知道怎么讲）
点分治的核心主要在于高效的分治，每一次都可以将所求区间大小缩短至 \(\dfrac{1}{k}\) 。
因此 \(T(n)=k\times T(n/k)\) ，根据主定理，时间复杂度为 \(O(n \log n)\) 。
分治的关键在于从在每一次操作的树上寻找重心，易证以重心为根的每颗子树大小不超过 \(\dfrac{n}{2}\) ，从而可以有效缩小操作区间，保证正确的复杂度。(其实感性也很好理解的来着)
例题
模板题，典中典。
两点间的路径分为两种：经过根的和不经过根的。
对于第二种我们在分治时可以统计到。
那么简单容斥一下就很清晰了：
- 先找到整棵树的重心，用桶统计所有经过重心的路径，更新答案。
- 分治，求出以重心为根的树的每颗子树的“小重心”，容斥一下发现不经过重心而经过小重心的路径即为在小重心所在子树中经过小重心的路径。(有点绕)
- 以此类推，直到每个点都成为过重心后，答案更新完成。
一些注意点：
- 桶中要随时保持 \(t_0=1\) ，因为都有不和其他路径组合的一种可能。
- 扶苏在这个帖子中提到关于时空间复杂的的问题。若一次统计的常数为 \(k_1\) ，点分治自身的常数为 \(k2\)，那么将询问在点分治内部统一更新的复杂度为 \(O((k_2+k_1)n\log n)\) ，每次分开更新的复杂度为 \(O(k_2k_1n\log n))\) , 显然后者大的多，故注意此实现细节。
Code
#include<bits/stdc++.h>
#define N 10005
#define M 10000005
using namespace std;
inline int read(){
int x=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x*w;
}
int root,n,m,tot,sum,cnt;
int head[N],q[N],dp[N],len[N],ans[N],cl[N],dis[N],siz[N];
int vis[N],t[M];
struct Edge{int to,next,w;}edge[N<<1];
void add(int u,int v,int w){
edge[++cnt]=(Edge){v,head[u],w};
head[u]=cnt;
}
void find(int x,int fa){
siz[x]=1; dp[x]=0;
for(int i=head[x];i;i=edge[i].next){
int v=edge[i].to;
if(vis[v]||v==fa) continue;
find(v,x);
dp[x]=max(dp[x],siz[v]);siz[x]+=siz[v];
}
dp[x]=max(dp[x],sum-siz[x]);
if(dp[x]<dp[root]) root=x;
}
void getdis(int x,int fa){
len[++tot]=dis[x];
for(int i=head[x];i;i=edge[i].next){
int v=edge[i].to;
if(v==fa||vis[v]) continue;
dis[v]=dis[x]+edge[i].w;
getdis(v,x);
}
}
void calm(int x){
int w=0;
for(int i=head[x];i;i=edge[i].next){
int v=edge[i].to;
if(vis[v]) continue;
tot=0; dis[v]=edge[i].w; getdis(v,x);
for(int j=1;j<=tot;++j)
for(int k=1;k<=m;++k)
if(q[k]>=len[j]) ans[k]|=t[q[k]-len[j]];
for(int j=1;j<=tot;++j)
if(len[j]<=1e7)cl[++w]=len[j],t[len[j]]=1;
}
for(int i=1;i<=w;++i) t[cl[i]]=0;
}
void solve(int x){
vis[x]=t[0]=1; calm(x);
for(int i=head[x];i;i=edge[i].next){
int v=edge[i].to;
if(vis[v]) continue;
root=0;dp[0]=n;sum=siz[v];
find(v,x);solve(root);
}
}
signed main(){
//freopen("P3806_7.in","r",stdin);
n=read();m=read();
for(int i=1;i<n;++i){
int u=read(),v=read(),w=read();
add(u,v,w);add(v,u,w);
}
for(int i=1;i<=m;++i) q[i]=read();
root=0;dp[0]=sum=n;
find(1,0); solve(root);
for(int i=1;i<=m;++i)
if(ans[i]) puts("AYE");
else puts("NAY");
//for(int i=1;i<=m;++i) printf("%d ",ans[i]);
return 0;
}