分治就是将一个问题划分成多个子问题来求解。
点分治就是在树上进行分治，一般是来统计路径信息的。
对于以 \(u\) 为根的子树内，所有的路径可以划分为两类，一类跨越了子树，经过了 \(u\)，另一类没有跨越，只经过子树中的点，而子树内的点又可以再分类，这就是点分治。
为了保证时间复杂度，每次需要选择子树中的重心来统计，保证了点分治的时间复杂度为 \(\mathcal{O}(n\log n)\)。
inline void findrt(int x,int fa,int cnt){
size[x]=1;int mx=0;
for(int i=head[x],y;i;i=e[i].next){
if(vis[y=e[i].v]||y==fa)continue;
findrt(y,x,cnt);
size[x]+=size[y];
mx=std::max(size[y],mx);
}
mx=std::max(mx,cnt-size[x]);
if(mx<=cnt/2)rt=x;
}
找根一次要找两遍，一遍找根，一遍统计正确的子树信息。
点分治有两种写法，一种是容斥统计，一种是分子树统计。
首先简单介绍一下容斥的写法
```cpp
inline void solve(int x){
vis[x]=1;ans+=calc(x,0);
for(int i=head[x];i;i=e[i].next){
int v=e[i].v;
if(vis[v])continue;
ans-=calc(x,dis[x]);
}
mp.clear();
for(int i=head[x];i;i=e[i].next){
int v=e[i].v;
if(vis[v])continue;
findrt(v,0,size[v]);
findrt(rt,0,size[v]);
solve(rt);
}
}
在第一次计算完根的贡献后，有一些贡献是不合法的（同一子树内结合），所以需要减去子树内在根的参数下的贡献。
分子树就是每遍历完一颗子树后计算它提供的贡献，计算完后在更新它的信息，这样保证了所有的贡献都是跨越子树的，每找完一个根后清空一下信息。
P3806 【模板】点分治 1
给定一棵有 \(n\) 个点的树，询问树上距离为 \(k\) 的点对是否存在。
拿 map 记一下到根的 \(dis\) 距离是否出现，然后直接分子树统计即可。
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=1e4+10;
int cmax,n,m,head[N],tot,rt,size[N],t,ans[N],q[N],dep[N],dis[N];
bool vis[N];
std::unordered_map<int,int> mp;
struct EDGE{int v,next,w;}e[N<<1];
inline void add(int u,int v,int w){e[++tot]={v,head[u],w},head[u]=tot;}
inline void findrt(int x,int fa,int cnt){
size[x]=1;int mx=0;
for(int i=head[x];i;i=e[i].next){
int v=e[i].v;
if(v==fa||vis[v])continue;
findrt(v,x,cnt);
size[x]+=size[v];
mx=std::max(mx,size[v]);
}
mx=std::max(mx,cnt-size[x]);
if(mx<cmax)rt=x,cmax=mx;
}
inline void clac(int x,int fa){
dep[++t]=x;
for(int i=head[x];i;i=e[i].next){
int v=e[i].v;
if(vis[v]||v==fa)continue;
dis[v]=dis[x]+e[i].w;
clac(v,x);
}
}
inline void solve(int x){
vis[x]=mp[0]=1;
for(int i=head[x];i;i=e[i].next){
int v=e[i].v;
if(vis[v])continue;
dis[v]=e[i].w;
clac(v,x);
for(int j=1;j<=m;++j)
for(int k=1;k<=t;++k)
if(mp.count(q[j]-dis[dep[k]]))ans[j]=1;
for(int j=1;j<=t;++j)mp[dis[dep[j]]]=1;
t=0;
}
mp.clear();
for(int i=head[x];i;i=e[i].next){
int v=e[i].v;
if(vis[v])continue;
cmax=1e9;findrt(v,0,size[v]);
findrt(rt,0,size[v]);
solve(rt);
}
}
signed main(){
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
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();
cmax=1e9;findrt(1,0,n);findrt(rt,0,n);
solve(rt);
for(int i=1;i<=m;++i)std::cout<<(ans[i]?"AYE\n":"NAY\n");
}