一道很水的树形dp吧。。。

这道题就是给你一棵树，然后允许你删除掉一些点和边，使得剩下的树的权值和最大。

与最大子序列类比，我们可以显然地得出：对于最大权值和为负数的子树，我们一定不会取。

所以我们可以定义一个状态：\(dp[i]\)表示结点\(i\)及其子树的最大权值和。

状态转移方程也很显然：\(dp[u] = w[u] + \sum{max(0, dp[v])}\)。注意子树的根节点是一定要取的。

最后的答案就是所有的dp取最大值。

为什么？

你取一个子树的最大值，相当于把他根以上的东西全部都剪掉，而下面是贪心取的，一定是最大值，所以没毛病。

代码：

#include
    
     #include
     
      const int maxn = 16005;struct Edges{    int next, to;} e[maxn << 1];int head[maxn], tot;int w[maxn];int res[maxn];int n, ans;void link(int u, int v){    e[++tot] = (Edges){head[u], v};    head[u] = tot;}void dfs(int u, int f){    res[u] = w[u];    for(int i = head[u]; i; i = e[i].next)    {        int v = e[i].to;        if(v == f) continue;        dfs(v, u);        res[u] += std::max(0, res[v]);    }}int main(){    scanf("%d", &n);    for(int i = 1; i <= n; i++) scanf("%d", &w[i]);    for(int i = 1; i < n; i++)    {        int x, y; scanf("%d%d", &x, &y);        link(x, y), link(y, x);    }    dfs(2, 0);    for(int i = 1; i <= n; i++)    {        //printf("%d ", res[i]);        ans = std::max(ans, res[i]);    }    printf("%d\n", ans);    return 0;}