【bzoj1316】【树上的询问】【点分治+map】

30%的数据，n≤100． 
100%的数据，n≤10000，p≤100，长度≤1000000． 

做完此题可看下POJ 3237 Tree

题解：

         用map记录一下某长度是否出现过,然后正常点分治即可.

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
#define N 10010
#define M 110
using namespace std;
set<int>s;
int n,m,x,y,v,cnt,sum,point[N],next[N<<1],ans[M],q[M],vis[N],dis[N],root,size[N],h[N];
struct edge{int st,en,v; 
}e[N<<1];
int read(){int x(0);char ch=getchar();while (ch<'0'||ch>'9') ch=getchar();while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x;
}
void add(int x,int y,int v){next[++cnt]=point[x];point[x]=cnt;e[cnt].st=x;e[cnt].en=y;e[cnt].v=v;
}
void dfs(int x,int fa){size[x]=1;h[x]=0;//cout<<x<<endl;for (int i=point[x];i;i=next[i])if (e[i].en!=fa&&!vis[e[i].en]){dfs(e[i].en,x);size[x]+=size[e[i].en];h[x]=max(h[x],size[e[i].en]);}h[x]=max(sum-size[x],h[x]);if (h[x]<h[root]) root=x; 
}
void getrace(int x,int fa,int v){s.insert(v);for (int i=point[x];i;i=next[i])if (!vis[e[i].en]&&e[i].en!=fa)getrace(e[i].en,x,v+e[i].v);  
}
void check(int x,int fa,int v){for (int i=1;i<=m;i++)if (s.find(q[i]-v)!=s.end()) ans[i]=1;for (int i=point[x];i;i=next[i])if (!vis[e[i].en]&&e[i].en!=fa)check(e[i].en,x,v+e[i].v);
}
void solve(int x){//cout<<x<<endl;vis[x]=1;s.clear();for (int i=point[x];i;i=next[i])if (!vis[e[i].en]){check(e[i].en,x,e[i].v);getrace(e[i].en,x,e[i].v);}for (int i=1;i<=m;i++) if (s.find(q[i])!=s.end()) ans[i]=1;for (int i=point[x];i;i=next[i])if (!vis[e[i].en]){root=0;sum=size[e[i].en];dfs(e[i].en,0);solve(root);}
}
int main(){//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);n=read();m=read();h[0]=n;for (int i=1;i<n;i++){x=read();y=read();v=read();add(x,y,v);add(y,x,v);} for (int i=1;i<=m;i++) q[i]=read();sum=n;dfs(1,0);//cout<<root<<endl;//for (int i=1;i<=n;i++) cout<<h[i]<<endl;solve(root);for (int i=1;i<=m;i++) if (ans[i]||q[i]==0) puts("Yes");else puts("No");
}