最大子树和

传送门

一道很简单的树形DP。

树形DP是啥？看名字就知道是在树上进行DP。树形DP的不同在于，对于一个节点，他的状态必然是由其子节点而不是其他节点转移过来的。

树形DP有啥技巧我也说不清……直接来几道题看看吧。

首先看这道题。这题就是要求在树中选取一棵子树，使得其权值和最大。

DP过程还是很显然的，用dp[i]表示在第i个节点能取到的最大权值，那么就有方程：

dp[i] = max(dp[i],dp[i] + dfs(e[i].to));其中dfs返回其子节点能取到的最大权值。

然后注意因为你一个子节点可能会取到负的权值，或者你递归返回的时候父亲会取到负值，所以我们直接在每次更新答案的时候都取依次最大就可以啦。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<queue>
#include<set>
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
#define enter putchar('
')

using namespace std;
typedef long long ll;
const int M = 50005;
const int INF = 1000000009;

int read()
{
    int ans = 0,op = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
    if(ch == '-') op = -1;
    ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
    ans *= 10;
    ans += ch - '0';
    ch = getchar();
    }
    return ans * op;
}

struct edge
{
    int next,to;
}e[M];

int n,val[M],a,b,ans = -2147483647,ecnt,head[M];
bool vis[M];

void add(int x,int y)
{
    e[++ecnt].to = y;
    e[ecnt].next = head[x];
    head[x] = ecnt;
}

int dfs(int x)
{
    vis[x] = 1;
    for(int i = head[x];i;i = e[i].next)
    {
    if(vis[e[i].to]) continue;
    val[x] = max(val[x],val[x] + dfs(e[i].to));
    }
    ans = max(ans,val[x]);
    return val[x];
}
int main()
{
    n = read();
    rep(i,1,n) val[i] = read();
    rep(i,1,n-1) a = read(),b = read(),add(a,b),add(b,a);
    dfs(1);
    printf("%d
",ans);
    return 0;
}