点分治
适合处理大规模的树上路径信息。
实现
取一个中心点计算跨过中心点的贡献。（lsy说得精辟但抽象）
先随便指定一个根 \(rt\)，我们能将树上的路径分为经过 \(rt\) 的路径和包含于 \(rt\) 的某棵子树内的路径（不经过 \(rt\)）。
对于经过当前根节点的路径，又可以分为两种，一种是以根节点为一个端点的路径，另一种是两个端点都不为根节点的路径。而后者又可以由两条属于前者的链合并得到。
接着我们枚举 \(rt\)，先计算在其子树中且经过该节点的路径对答案的贡献，再递归其子树对不经过该节点的路径进行求解。
OI-wiki说着有点抽象，其实就是不断地在上一个中心点的子树中去取一个新中心点，然后一直去求解某一类路径，就是一个分治的思想。
然后随便找一个中心点的话如果树是一条链这个分治就会退化为 \(O(n^{\mathbf 2})\)，所以我们要让递归层数尽量少，管的什么证明反正就是取树的重心。重心定义不再赘述，写下求法：记录 \(maxp[u]\) 表示删掉 \(u\) 之后产生的最大子树大小，重心就是 \(maxp\) 最小的点。下面是求法：
点击查看代码
void find(ll u,ll fa){
siz[u]=1,maxp[u]=0;
for(int i=head[u];i;i=e[i].next){
ll v=e[i].to;
if(v==fa||vis[v]) continue;
find(v,u);
siz[u]+=siz[v];
maxp[u]=max(maxp[u],siz[v]);
}
maxp[u]=max(maxp[u],sums-siz[u]); //sums是会变的子树总大小，会在分治过程中变为siz[v]
if(maxp[u]<maxp[rt]) rt=u;
}
结合具体题目来分治。
题
P3806 【模板】点分治 1
首先离线询问省得每次都搞一遍淀粉质，然后先找到重心然后开始分治。每次求答案就把重心子树内的点到重心的距离求出来，然后枚举询问看有没有点的距离满足询问，这里具体是这样判的：开一个数组 \(flag_i\) 表示有没有点到重心的距离为 \(i\)，if(q[k]>=dist[j]&&!ans[k]) ans[k]=fl[q[k]-dist[j]];。
然后我们要记得清空这个 \(flag\) 数组，于是考虑开一个桶记录哪些 \(i\) 修改过。但是这里有些细节问题，\(dis[j]\) 可能太大了就会爆掉桶，所以要特判一下。
还有一些细节：我们每一次重新找重心都是先设为 \(\mathbf 0\)，然后树总的大小就变成了 \(siz[v]\)，因为我们是进入 \(v\) 的子树来分治的；一开始 \(flag_{\mathbf{0}}\) 就要设成 \(\mathbf 1\)，毕竟也可能一个点和中心的距离直接就是询问值；然后数组开大，还有点细节看代码吧。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=114514,M=10000005; //注意数据范围
struct xx{
ll next,to,val;
}e[2*N];
ll head[2*N],cnt;
void add(ll x,ll y,ll z){
e[++cnt].next=head[x];
e[cnt].to=y;
e[cnt].val=z;
head[x]=cnt;
}
ll n,m,q[N],rt,sums;
ll siz[N],dis[N],maxp[N];
bool vis[N],fl[M],ans[M];
ll bu[M],tot;
void find(ll u,ll fa){
siz[u]=1,maxp[u]=0;
for(int i=head[u];i;i=e[i].next){
ll v=e[i].to;
if(v==fa||vis[v]) continue;
find(v,u);
siz[u]+=siz[v];
maxp[u]=max(maxp[u],siz[v]);
}
maxp[u]=max(maxp[u],sums-siz[u]);
if(maxp[u]<maxp[rt]) rt=u;
}
ll res,dist[N];
void dfs_dis(ll u,ll fa){
dist[++res]=dis[u];
for(int i=head[u];i;i=e[i].next){
ll v=e[i].to,w=e[i].val;
if(v==fa||vis[v]) continue;
dis[v]=dis[u]+w;
dfs_dis(v,u);
}
}
void calc(ll u){
tot=0;
for(int i=head[u];i;i=e[i].next){
ll v=e[i].to,w=e[i].val;
if(vis[v]) continue;
res=0,dis[v]=w;
dfs_dis(v,u);
for(int j=1;j<=res;++j) //枚举点
for(int k=1;k<=m;++k)//枚举询问
if(q[k]>=dist[j]&&!ans[k]) ans[k]=fl[q[k]-dist[j]];
for(int j=1;j<=res;++j)
if(dist[j]<=1e7) bu[++tot]=dist[j],fl[dist[j]]=1;
}
for(int i=1;i<=tot;++i) fl[bu[i]]=0;
}
void solve(ll u){
vis[u]=1;
calc(u);
for(int i=head[u];i;i=e[i].next){
ll v=e[i].to;
if(vis[v]) continue;
rt=0,maxp[rt]=N,sums=siz[v];
find(v,0),solve(rt);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m; sums=n;
for(int i=1;i<n;++i){
ll a,b,c;
cin>>a>>b>>c;
add(a,b,c),add(b,a,c);
}
for(int i=1;i<=m;++i) cin>>q[i];
rt=0,sums=maxp[rt]=n,fl[0]=1;
find(1,0),solve(rt);
for(int i=1;i<=m;++i)
if(ans[i]) cout<<"AYE\n";
else cout<<"NAY\n";
return 0;
}