whust 2016 warm up C ||codeforces 682 C. Alyona and the Tree (最大连续和,树形dp)

cf682C题目链接

 

题意:给一棵树。。有点权和边权。。。如果一个点v的子树中存在某点u,满足dis(u,v)>a[u],那么点v就非常sad…

dis(u,v)表示点u到v的距离。。。a[u]是u的点权。。现在问最少要删除多少个叶子节点才能使得没有点节点感到sad..

 

思路:dfs一下。。。需要注意的是边权有负数。。。所以类似于区间的最大连续区间和。。。我们也也可以维护在树上的最大连续和。。。只需要如果当前为负就变成0即可。。。

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz