传送门 Solution: 考虑倍增，维护up和w数组，up[i][j]代表i节点向上跳2^j能到达的节点，w[i][j]代表i节点及其以上2^j的和，一遍dfs，常规倍增处理即可。 特别地，w[i][0]的值不是val[father]，而是val[i]
#include<bits/stdc++.h> #define N 100005 using namespace std; int n,s,val[N],tot,first[N],depth[N],ans; int up[N][20],w[N][20]; struct node { int to,next; }edge[2*N]; inline void addedge(int x,int y) { ++tot; edge[tot].to=y; edge[tot].next=first[x]; first[x]=tot; } inline void dfs(int now,int fa) { up[now][0]=fa; w[now][0]=val[now]; for(int i=1;i<=19;i++) { up[now][i]=up[up[now][i-1]][i-1]; w[now][i]=w[now][i-1]+w[up[now][i-1]][i-1]; } int x=now; int remain=s; for(int i=19;i>=0;i--) { if(up[x][i]&&w[x][i]<remain){ remain=remain-w[x][i]; x=up[x][i];//注意这两句话的顺序 } } if(w[x][0]==remain) ans++; for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(vis==fa) continue; dfs(vis,now); } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>s; for(int i=1;i<=n;i++) cin>>val[i]; for(int i=1;i<=n-1;i++) { int x,y; cin>>x>>y; addedge(x,y); addedge(y,x); } dfs(1,0); cout<<ans; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9388242.html
