20pts求助(玄关)
查看原帖
20pts求助(玄关)
950272
__Segment__楼主2025/8/1 15:29

rt.#3#6AC,其余WA

#include <bits/stdc++.h>
using namespace std;
const int N = 6e3 + 5;

int a[N], n, f[N][2];
bool vis[N];
vector <int> G[N];

void dfs(int step) {
	f[step][0] = 0;
	f[step][1] = a[step];
	for (int i : G[step]) {
		dfs(G[step][i]);
		f[step][0] += max(f[G[step][i]][0], f[G[step][i]][1]);
		f[step][1] += f[G[step][i]][0];
	}
	return;
}

int main() {
	cin >> 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[v].push_back(u);
		vis[u] = true;
	}
	
	int root;
	for (int i = 1; i <= n; ++i)
		if (!vis[i]) {
			root = i;
			break;
		}
	
	dfs(root);
	
	cout << max(f[root][0], f[root][1]) << endl;
}
2025/8/1 15:29
加载中...