对于100%数据，N≤100000，，所有权值以及S都不超过1000。
题解：处理一下每个点到根的路径权值和，动态的维护一个set，每dfs到一个点询问一下set里有没有当前点到根的路径权值和-s的点。有的话答案+1即可。
#include<iostream>#include<cstdio>#include<set>#define N 100010using namespace std;set<int>s;int n,m,point[N],next[N*2],k,a[N],u,v,cnt,ans,deep[N];struct use{int st,en;}e[2*N];void add(int x,int y){next[++cnt]=point[x];point[x]=cnt;e[cnt].st=x;e[cnt].en=y;}void dfs(int x,int fa){for (int i=point[x];i;i=next[i]) if (e[i].en!=fa) { deep[e[i].en]=deep[x]+a[e[i].en]; s.insert(deep[e[i].en]);if (s.find(deep[e[i].en]-k)!=s.end()) ans++;dfs(e[i].en,x);s.erase(deep[e[i].en]);}}int main(){scanf("%d%d",&n,&k);for (int i=1;i<=n;i++) scanf("%d",&a[i]);for (int i=1;i<=n-1;i++) {scanf("%d%d",&u,&v);add(u,v);add(v,u); }s.insert(0);deep[1]=a[1];s.insert(deep[1]);dfs(1,0);cout<<ans<<endl;}
因为你的喜爱会挡也挡不住地流露出来。
