The 2021 ICPC Asia Nanjing Regional Contest H.Crystalfly(树上DP)

cjb的题解

有一个容易被忘记的坑点:
在我们锁定最大点w，然后对其他点进行第二种决策的计算时,要记得还要反过来拿其他店对w点进行一轮第二种决策的计算!!!
还有别忘了if(i==fa)continue!!!
另外vector里的pair的second是没有用的,可以忽略

#include <bits/stdc  .h>
#define int long long
#define endl '\n'
using namespace std;
int n;
const int N = 1e5   10;
int a[N];
int t[N];
vector<pair<int, int>>g[N];
int sum[N], f[N];

void dfs(int u, int fa) {
	int aim = 0;
	int t1 = 0, t2 = 0;
	if (g[u].size() == 1 && fa != -1) {
		return;
	}
	for (auto i : g[u]) {
		if (i.first == fa)
			continue;
		dfs(i.first, u);
		sum[u]  = f[i.first];
	}
	for (auto i : g[u]) {//第一种决策
		if (i.first == fa)
			continue;
		t1 = max(t1, sum[u]   a[i.first]);
	}
	int maxw = 0, w = 0;

	for (auto i : g[u]) {//找到w
		if (i.first != fa && t[i.first] == 3 && a[i.first] > maxw) {
			maxw = a[i.first];
			w = i.first;
		}
	}

	if (w != 0)
		for (int j = 0; j < g[u].size(); j  ) {//用w对其他点一轮转移
			if (g[u][j].first == fa)
				continue;
			int v = g[u][j].first;
			if (w == v)
				continue;
			t2 = max(t2, sum[u] - f[v]   a[v]   sum[v]   a[w]);
		}
	for (int j = 0; j < g[u].size(); j  ) {//还要其他点对w进行一轮转移
		if (g[u][j].first == fa)
			continue;
		int v = g[u][j].first;
		if (v == w)
			continue;
		if (t[v] == 3) {
			t2 = max(t2, sum[u] - f[w]   a[w]   sum[w]   a[v]);
		}
	}
	f[u] = max(t1, t2);
}

void init() {
	for (int i = 1; i <= n; i  ) {
		f[i] = 0;
		sum[i] = 0;
	}
	for (int i = 1; i <= n; i  )
		g[i].clear();
}

void solve() {
	cin >> n;
	init();
	for (int i = 1; i <= n; i  )
		cin >> a[i];
	for (int i = 1; i <= n; i  )
		cin >> t[i];
	for (int i = 1; i <= n - 1; i  ) {
		int u, v;
		cin >> u >> v;
		g[u].push_back({v, a[v]});//没有意义
		g[v].push_back({u, a[u]});
	}
	dfs(1, -1);
	cout << f[1]   a[1] << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t--)
		solve();
	return 0;
}

这篇好文章是转载于：学新通技术网