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],不行就把整棵子树删掉。

代码