蓝桥系列
树形DP / dfs
题意:求给定图的有最大和的连通子图。
定义dp[u]为u为根结点的子树中, 包含u的连通子图的最大和。
假设u有直接子结点$[s_1, s_2, …, s_n]$, 则$dp[u] = val[u] + \sum dp[s_j], dp[s_j] > 0$
在dfs过程中实时以dp[u]更新res
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
int a[N], h[N], e[N << 1], ne[N << 1], idx;
ll res = -1e9;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
ll dfs(int u, int last) {
ll mx = a[u];
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (j == last) continue;
ll x = dfs(j, u);
if (x > 0) mx += x;
}
res = max(res, mx);
return mx;
}
int main () {
int n; cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i], h[i] = -1;
for (int i = 1; i < n; i ++) {
int a, b; cin >> a >> b;
add(a, b), add(b, a);
}
dfs(1, 0);
cout << res << endl;
return 0;
}