C++14(g++5.4) 解法, 执行用时: 7ms, 内存消耗: 1396K, 提交时间: 2019-10-26 22:05:31

#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio> 
#define maxn 10000
using namespace std;
vector<int>G[maxn];
int list[maxn];
void insert(int be,int en){
	G[be].push_back(en);
}
int n,m;
int vis[maxn];
int f[maxn];
int g[maxn];
int dfs(int x,int fa){
	vis[x] =1;
	int a = 0;
	int b = 0;
	for(int i=0;i<G[x].size();i++){
		int p = G[x][i];
		if(p == fa) continue;
		dfs(p,x);
		f[x] += max(f[p],g[p]);
		g[x] += f[p];
	}
	
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&list[i]);
		g[i] = list[i];
	}
	int be,en;
	for(int i=0;i<n;i++){
		scanf("%d %d",&be,&en);
		if(be == en && en == 0) continue;
		insert(be,en);
		insert(en,be);
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			dfs(i,-1);
			printf("%d\n",max(g[i],f[i]));
		}	
	}
	
	return 0;
} 

C++ 解法, 执行用时: 37ms, 内存消耗: 32144K, 提交时间: 2022-06-21 21:21:09

#include<bits/stdc++.h>
using namespace std;
int n;
struct node
{
	int x,isroot;
	vector<int> son;
}s[1000001];
int f[1000001][2];
void dfs(int x)
{
	f[x][0]=0;
	f[x][1]=s[x].x;
	for (int i=0;i<s[x].son.size();i++){
		dfs(s[x].son[i]);
		f[x][0]+=max(f[s[x].son[i]][0],f[s[x].son[i]][1]);
		f[x][1]+=f[s[x].son[i]][0];
	}
}
int main(){
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>s[i].x;
		s[i].isroot=1;
	}
	while(1){
		int x,y;
		cin>>x>>y;
		if(x==0&&y==x)break;
		s[y].son.push_back(x);
		s[x].isroot=0;
	}
	for (int i=1;i<=n;i++){
		if (s[i].isroot){
			dfs(i);
			cout<<max(f[i][0],f[i][1]);
			return 0;
		}
	}
}