G 小苯的树上操作

容易看出是换根dp，我们可以这样定义：

  • 表示以 为根的子树， 不去掉的最大点权和
  • 和 分别表示在以 为根的子树中，只保留一颗子树的最大权值和次大权值(不包括 的权值)
  • 表示以 为根， 不去掉的最大点权和
  • 和 分别表示在以 为根时，只保留一条相连的边的最大权值和次大权值(不包括 的权值)

接下来考虑转移

我们设当前树的根是 ，遍历到 时，设 有 个孩子，其中 的第 个孩子为

在求 时，考虑从某个孩子 转移过来，可以考虑保留 节点，从 转移过来；也可以不保留 节点，直接去掉整个子树，也就是 ；还可以从 的最大子树转移过来（对应题目中的第二种操作），也就是 。以上这些取 即可。

在求 和 的时候，也和刚刚一样，用 来更新即可。

在求 的时候，设 的父节点是 ， 首先默认 ，然后考虑加上 相关的值。 如果带上 本身，那么值是 ，但是这其中可能会有 相关的值，也就是 ，需要减去；如果不带上 ，那么值就是 。

但是这个值有可能就是 的子树的权值和，如果发现是的话，就要用 来更新，以上取一个 后加上即可。

在求 和 的时候，也和刚刚一样，用上面算出来的值更新即可。

时间复杂度 

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;

int a[N];
LL dp1[N][3], dp2[N][3];
vector<int> g[N];

void init(int n) {
	for (int i = 1; i <= n; i ++ ) {
		g[i].clear();
		for (int j = 0; j < 3; j ++ ) 
			dp1[i][j] = dp2[i][j] = 0;
	}
}
void dfs1(int u, int last) {
	dp1[u][2] = a[u];
	for (int v : g[u]) {
		if (v == last) continue;
		dfs1(v, u);
		LL val = max(dp1[v][2], dp1[v][0]);
		if (val > 0) dp1[u][2] += val;
		if (val > dp1[u][0]) {
			dp1[u][1] = dp1[u][0];
			dp1[u][0] = val;
		} else if (dp1[v][2] > dp1[u][1]) {
			dp1[u][1] = val;
		}
	}
}
void dfs2(int u, int last) {
	for (int v : g[u]) {
		if (v == last) continue;
		dp2[v][0] = dp1[v][0];
		dp2[v][1] = dp1[v][1];
		dp2[v][2] = dp1[v][2];
		LL val1 = dp2[u][2];
		LL tmp = max(dp1[v][0], dp1[v][2]);
		if (tmp > 0) val1 -= tmp;
		LL val2 = dp2[u][0];
		if (dp2[u][0] == tmp) val2 = dp2[u][1];
		LL val = max(val1, val2);
		dp2[v][2] += val;
		if (val > dp2[v][0]) {
			dp2[v][1] = dp2[v][0];
			dp2[v][0] = val;
		} else if (val > dp2[v][1]) {
			dp2[v][1] = val;
		}
		dfs2(v, u);
	}
}

void solve() {
	int n; cin >> n;
	init(n);
	for (int i = 1; i <= n; i ++ ) cin >> a[i];
	for (int i = 1; i < n; i ++ ) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs1(1, 0);
	dp2[1][0] = dp1[1][0];
	dp2[1][1] = dp1[1][1];
	dp2[1][2] = dp1[1][2];
	dfs2(1, 0);
	LL ans = 0;
	for (int i = 1; i <= n; i ++ ) ans = max(ans, dp2[i][2]);
	cout << ans << endl;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
	freopen("1.out", "w", stdout);
#endif
	int T; cin >> T;
	while (T -- ) solve();
	return 0;
}