【传送门：BZOJ1316】
简要题意：
给出一棵n个点的带边权有根树
有q个询问，每个询问输入len，判断在树上是否存在长度为len的路径
题解：
直接点分治，用set保存链的长度就行了
参考代码：
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<set> #define Maxn 11000 #define INF 1<<30 using namespace std; struct node{int x,y,d,next;}a[Maxn*2];int len,last[Maxn]; void ins(int x,int y,int c){a[++len]=(node){x,y,c,last[x]};last[x]=len;} int ms[Maxn],sum,tot[Maxn],rt; bool v[Maxn]; set<int> S; void getrt(int x,int fa) { tot[x]=1;ms[x]=0; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(y==fa||v[y]==true) continue; getrt(y,x); tot[x]+=tot[y]; ms[x]=max(ms[x],tot[y]); } ms[x]=max(ms[x],sum-tot[x]); if(ms[x]<ms[rt]) rt=x; } int dep[Maxn],Q,q[Maxn]; int p[Maxn]; void cal(int x,int fa,int d) { for(int i=1;i<=Q;i++) if(S.find(q[i]-d)!=S.end()) p[i]=true; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(y==fa||v[y]==true) continue; cal(y,x,d+a[k].d); } } void add(int x,int fa,int d) { S.insert(d); for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(y==fa||v[y]==true) continue; add(y,x,d+a[k].d); } } void solve(int x) { v[x]=true;S.insert(0); for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(v[y]==true) continue; cal(y,x,a[k].d); add(y,x,a[k].d); } S.clear(); for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(v[y]==true) continue; rt=0;sum=tot[y];getrt(y,x); solve(rt); } } int main() { int n; scanf("%d%d",&n,&Q); len=0;memset(last,0,sizeof(last)); for(int i=1;i<n;i++) { int x,y,c; scanf("%d%d%d",&x,&y,&c); ins(x,y,c);ins(y,x,c); } memset(v,false,sizeof(v)); rt=0;sum=ms[rt]=n;getrt(1,0); memset(p,false,sizeof(p)); for(int i=1;i<=Q;i++) scanf("%d",&q[i]); solve(rt); for(int i=1;i<=Q;i++) { if(p[i]==true||q[i]==0) printf("Yes "); else printf("No "); } return 0; }