一道比较好想的树形\(DP\)
完全可以用树形DP的基本思路,递归,然后取最优的方法。
\(Code\)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
int n, a, b, cnt, maxn, data[100100], dp[100100], lin[100010];
struct cym {
int to, nex;
}e[100100];
inline void add(int f, int t)
{
e[++cnt].to = t;
e[cnt].nex = lin[f];
lin[f] = cnt;
}
inline void dfs(int now, int fa)
{
dp[now] = data[now];
for (int i = lin[now]; i; i = e[i].nex)
{
int to = e[i].to;
if (to == fa) continue;
dfs(to, now);
dp[now] += max(0, dp[to]);
}
maxn = max(maxn, dp[now]);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &data[i]), dp[i] = data[i];
for (int i = 1; i < n; i++)
{
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
dfs(1, 0);
/* for (int i = 1; i <= n; i++)
if (!dp[i])
dfs(i, 0);
*/
printf("%d", maxn);
}