不难发现树上的路径分为两类，经过根节点 $r t$ 的路径和包含于 $r t$ 的某棵子树里(不经过 $r t$ )的
对于前者，我们用 $d i s [u]$ 表示结点u到根节点 $r t$ 的路径长度，则 $u$ 到 $v$ 的路径长即为 $d i s [u] + d i s [v]$
对于后者，既然 $u$ 到 $v$ 的路径包含在 $r t$ 的某个子树内，那么我们就找到这棵子树的根，再对他求一次第一类路径
这样分治的思想就很明显了
就是把原来的树分成很多小的子树，并对每个子树分别求解第一类路径— $f r o m$ $n i i i c k$

Code

写之前总觉得 $v i s$ 数组可以省略，因为一般 $d f s$ 时保存一下父亲就行了，保证一直向下搜
写之后才发现每次是找重心的，所以和一般的 $d f s$ 不一样
然后 $g e t r t ()$ 和 $g e t d i s ()$ 两个函数会访问 $v i s$ 还没标记的点，所以要记录 $f a$
$s o l v e ()$ 不存在这种情况，所以不用

#include<bits/stdc++.h>
using namespace std;
const int N=10002;
struct node{
	int to,ne,w;
}e[N<<1];
int h[N],sum,mx[N],sz[N],dis[N],rem[N],tot,x,y,z,i,que[52],rt,n,m,q[N];
bool vis[N],jud[10000002],ans[52];
inline char gc(){
	static char buf[100000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd(){
	int x=0,fl=1;char ch=gc();
	for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
	for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
	return x*fl;
}
void add(int x,int y,int z){e[++tot]=(node){y,h[x],z},h[x]=tot;}
void getrt(int u,int fa){
	sz[u]=1,mx[u]=0;//这句不加也能过，但其他题目就过不去了
	for (int i=h[u],v;i;i=e[i].ne)
		if ((v=e[i].to)!=fa && !vis[v]){
			getrt(v,u);
			sz[u]+=sz[v];
			mx[u]=max(mx[u],sz[v]);
		}
	mx[u]=max(mx[u],sum-sz[u]);
	if (mx[u]<mx[rt]) rt=u;
}
void getdis(int u,int fa){
	rem[++rem[0]]=dis[u];//这里在做其他题目的时候最好判一下是否<=max{k}，不然可能RE
	for (int i=h[u],v;i;i=e[i].ne)
		if ((v=e[i].to)!=fa && !vis[v]){
			dis[v]=dis[u]+e[i].w;
			getdis(v,u);
		}
}
void calc(int u){
	int p=0;
	for (int i=h[u],v;i;i=e[i].ne)
		if (!vis[v=e[i].to]){
			rem[0]=0,dis[v]=e[i].w;
			getdis(v,0);
			for (int j=1;j<=rem[0];j++)
				for (int k=1;k<=m;k++)
					if (que[k]>=rem[j]) ans[k]|=jud[que[k]-rem[j]];
			for (int j=1;j<=rem[0];j++) q[++p]=rem[j],jud[rem[j]]=1;
		}
	for (int i=1;i<=p;i++) jud[q[i]]=0;
}
void solve(int u){
	vis[u]=jud[0]=1,calc(u);
	for (int i=h[u],v;i;i=e[i].ne)
		if (!vis[v=e[i].to]){
			sum=sz[v],mx[rt=0]=1e9;
			getrt(v,0);
			solve(rt);
		}
}
int main(){
	n=rd(),m=rd();
	for (i=1;i<n;i++) x=rd(),y=rd(),z=rd(),add(x,y,z),add(y,x,z);
	for (i=1;i<=m;i++) que[i]=rd();
	sum=mx[rt=0]=n;
	getrt(1,0);
	solve(rt);
	for (i=1;i<=m;i++) puts(ans[i]?"AYE":"NAY");
}

洛谷P3806 【模板】点分治1

Code