$large{先说好，因为本人比较菜，只能口胡一下板子了，有什么优（毒）秀（瘤）的题后期再更吧……}$
淀粉质，是一种很好吃的高能量食品，但如果不及时消化，就会消化不良（大雾）
首先考虑一下，不管怎么做，总要从脑袋到脚，跑个树高，而这又是个无根树
于是我们就抛出了我们树的重心：
- 利用$DFS$找到每个节点下面子树顺序的大小（包括自己），同时用整棵树的大小减去这个值求出这个节点另一边的大小（不理解的话可以画图理解一下QQwQ）
如上图，当我们在计算$2$节点时会计算其子树大小（为4），并用总数减子树大小（为6），再取$max$
像这样不停的找一个两边比较平衡的节点就可以找到中心，代码如下：
inline void FocFind(int pos,int fa) { maxn[pos]=0;size[pos]=1; for(int i=head[pos];i;i=edge[i].next) if(!vis[edge[i].to]&&edge[i].to!=fa) { FocFind(edge[i].to,pos); size[pos]+=size[edge[i].to]; maxn[pos]=max(maxn[pos],size[edge[i].to]); } maxn[pos]=max(maxn[pos],sum-size[pos]); if(maxn[foc]>maxn[pos]) foc=pos; }
(初始化我就不写了，反正很水)
通过找树的重心，我们完美的将每次要分治的树抖成了$Log$的高度（想想都有点小兴奋呢）
题目要求每次询问两点之间长度为$c$的路径是否存在，因此我们可以先预处理出存在的路径长度。
考虑每次分治一棵树时我们应该做什么。
显然因为我们是分治，所以要处理出当前树的根（即重心）到每个点之间的距离并存下来（不用考虑顺序），同时开一个$judge$来记录一种距离是否出现。跑完当前树的根的一棵子树后跑一遍距离，检查一下每个距离和$c$的差是否出现过就可以了，如果看不懂可以自行画图理解一下。
上代码：
#include<bits/stdc++.h> using namespace std; inline int read() { int f=1,w=0;char x=0; while(x<'0'||x>'9') {if(x=='-') f=-1; x=getchar();} while(x!=EOF&&x>='0'&&x<='9') {w=(w<<3)+(w<<1)+(x^48);x=getchar();} return w*f; } int check[10000001],judge[10000001]; int head[400004],num_edge,n,m,sum,Q[100001],now[100001]; int size[100001],foc,dis[100001],vis[100001],road[100001],maxn[100001]; struct Edge{int next,to,dis;} edge[400004]; inline void add(int from,int to,int dis) { edge[++num_edge].next=head[from]; edge[num_edge].to=to; edge[num_edge].dis=dis; head[from]=num_edge; } inline void FocFind(int pos,int fa) { maxn[pos]=0;size[pos]=1; for(int i=head[pos];i;i=edge[i].next) if(!vis[edge[i].to]&&edge[i].to!=fa) { FocFind(edge[i].to,pos); size[pos]+=size[edge[i].to]; maxn[pos]=max(maxn[pos],size[edge[i].to]); } maxn[pos]=max(maxn[pos],sum-size[pos]); if(maxn[foc]>maxn[pos]) foc=pos; } inline void GetDis(int pos,int fa) { road[++road[0]]=dis[pos]; for(int i=head[pos];i;i=edge[i].next) if(edge[i].to!=fa&&!vis[edge[i].to]) { dis[edge[i].to]=dis[pos]+edge[i].dis; GetDis(edge[i].to,pos); } } inline void AnsForSon(int pos) { int tot=0; for(int i=head[pos];i;i=edge[i].next) if(!vis[edge[i].to]) { dis[edge[i].to]=edge[i].dis; road[0]=0; GetDis(edge[i].to,pos); for(int j=road[0];j;j--) for(int k=1;k<=m;k++) if(Q[k]-road[j]>=0) check[k]|=judge[Q[k]-road[j]]; for(int j=road[0];j;j--) now[++tot]=road[j],judge[road[j]]=1; } for(int i=1;i<=tot;i++) judge[now[i]]=0; } inline void Solve(int pos) { vis[pos]=judge[0]=1;AnsForSon(pos); for(int i=head[pos];i;i=edge[i].next) if(!vis[edge[i].to]) { sum=size[edge[i].to];maxn[foc=0]=0x3f3f3f3f; FocFind(edge[i].to,0);Solve(foc); } } int main(){ n=read(),m=read(); for(int i=1;i<n;i++) { int u=read(),v=read(),d=read(); add(u,v,d),add(v,u,d); } for(int i=1;i<=m;i++) Q[i]=read(); maxn[foc]=sum=n; FocFind(1,0); Solve(foc); for(int i=1;i<=m;i++) if(check[i]) puts("AYE"); else puts("NAY"); }
注意，点分治的过程中相当于弱化了原来的树的结构，因此在理解时不要太过在意父子关系，主要理解$vis$就好