hdu 1520 Anniversary party (树形dp模板题)

题目链接
题意:一个舞会,每个人有一个val,给出n个人之间的领导和被领导关系,一个人不愿意与他的领导同时参加,问一种安排方案,使得参加的人的val和最大,问这个最大的和是多少。

思路:树形dp模板题。

dp1[v]表示包含v节点的子树的最大值。

dp2[v]表示,不包含v节点的[……]

Read more

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的点权。。现在问最少要删除多少个叶子节点才能使得没有点节点感[……]

Read more

hdu 2196 Computer (树的直径||树形dp)

hdu2196

题意:给出一棵树。。。求距离每个点的最远距离是多少。。。

思路:最远距离什么的。。能想到树的直径。。。但是有什么关系呢? 我们在求树的直径的时候。。。直径的两个端点是可以知道的。。。如果再从两个端点分别做两次bfs。。。每个点取两个距离的较大值就是答案。。。。?

1[……]

Read more