原题：点击打开链接
给你一棵树，1为该树的根只要有任意一条到i的路径是大于num[i]，就要将该点和该点子树删掉。
从1开始搜索路径，取一到任意点的最大路径，若最大路径大于num[i]，则可以将该点与子树删除。当路径为负数时要清零。
#include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <iostream> #include <vector> using namespace std; const int maxn=1e5+5; vector<int> s[maxn],w[maxn],c[maxn]; int n,sum,num[maxn],vis[maxn],viss[maxn],k,flag; long long w1[maxn],wmax[maxn]; void dfs2(int u) { for(int i=0;i<s[u].size();i++) { if(!vis[s[u][i]]) vis[s[u][i]]=1; dfs2(s[u][i]); } } void dfs1(int u) { for(int i=0;i<s[u].size();i++) { int v=s[u][i]; if(vis[v]) continue; w1[v]=w1[u]+w[u][i]; wmax[v]=max(wmax[v],w1[v]); if(w1[v]<0) w1[v]=0; if(wmax[v]>num[v]){ vis[v]=1; dfs2(v); } if(!vis[v]) dfs1(v); } } int main() { int n; while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) { int a; scanf("%d",&a); num[i]=a; } for(int i=1;i<=n-1;i++) { int a,b; scanf("%d%d",&a,&b); s[a].push_back(i+1); w[a].push_back(b); // c[a].push_back(i+1); } sum=0; memset(vis,0,sizeof(vis)); memset(w1,0,sizeof(w1)); memset(wmax,0,sizeof(wmax)); dfs1(1); for(int i=2;i<=n;i++) if(vis[i]) sum++; printf("%d\n",sum); } }
