CF #358 C. Alyona and the Tree
传送门：http://codeforces.com/contest/682/problem/C
题目大意
有一颗根为节点1的树，每条边有一个权值，每个点有一个a[i]值，对于一个节点V如果存在节点U使，V~U的路径长度大于a[V]，那么说明节点V是sad的。问要删除多少节点，才能使这棵树是不Sad的。
题解
统计每一个节点到根的最大后缀和，然后比较后缀和和a[i]，不行就把整棵子树删掉。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include #include using namespace std; const int Maxn=100000; int n; struct Edge{ int v,nxt; int w; Edge(){} Edge(int v0,int w0,int n0){ v=v0; w=w0; nxt=n0; } }; int head[Maxn+5]; Edge e[Maxn*2+10]; int nume; long long dp[Maxn+5]; int a[Maxn+5]; int siz[Maxn+5]; int Ans; void TreeDp(int x,long long val){ dp[x]=val; siz[x]=1; for (int i=head[x];i;i=e[i].nxt){ int v=e[i].v; int w=e[i].w; if (val+(long long)w > 0){ TreeDp(v,val+(long long)w); }else{ TreeDp(v,0); } siz[x]+=siz[v]; } } void getAns(int x){ if (dp[x]>a[x]){ Ans+=siz[x]; return ; } for (int i=head[x];i;i=e[i].nxt){ getAns(e[i].v); } } int main(){ scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); for (int i=2;i<=n;i++){ int v,w; scanf("%d%d",&v,&w); e[++nume]=Edge(i,w,head[v]); head[v]=nume; } TreeDp(1,0); getAns(1); printf("%d\n",Ans); return 0; } |
原文链接：CF #358 C. Alyona and the Tree
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!