AcWing 1220. 生命之树
原题链接
中等
作者:
追风小小少年
,
2024-04-20 23:12:39
,
所有人可见
,
阅读 1
算法1
树形dp
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 100;
int n, w[N], f[N];
long long dp[N];
int e[N], h[N], ne[N], idx;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u)
{
f[u] = 1;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!f[j])
{
dfs(j);
if (dp[j] > 0)
dp[u] += dp[j]; // 状态递归
}
}
}
int main()
{
cin >> n;
memset(h, -1, sizeof(h));
for (int i = 1; i <= n; i++)
{
cin >> w[i];
dp[i] = w[i];
}
for (int i = 1; i < n; i++)
{
int a, b;
cin >> a >> b;
add(a, b); add(b, a);
}
dfs(1);
long long res = -0x3f3f;
for (int i = 1; i <= n; i++)
res = max(res, dp[i]);
cout << res << endl;
return 0;
}