算法训练 结点选择

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 100000 + 5;
int m, cnt = 0;
int y[maxn] = {0}, n[maxn] = {0}, w[maxn], head[maxn] = {0}, vis[maxn] = {0}; 

struct ArcNode
{
	int vex, next;
}list[2 * maxn];

//插入边，插成对称的 

void Insert(int u, int v)
{
	list[++cnt].vex = v;
	list[cnt].next = head[u];
	head[u] = cnt;
	list[++cnt].vex = u;
	list[cnt].next = head[v];
	head[v] = cnt;
}

void Dp(int root)
{
	vis[root] = 1;
	for(int i = head[root]; i != 0; i = list[i].next)
	{
		if(vis[list[i].vex] == 0)
		{
			Dp(list[i].vex);
			y[root] += n[list[i].vex];
			n[root] += max(y[list[i].vex], n[list[i].vex]);
		}
	}
	y[root] += w[root];
}

int main()
{
	int i, j, u, v, ans;
	scanf("%d", &m);
	for(i = 1; i <= m; i++)
		scanf("%d", &w[i]);
	for(j = 1; j <= m - 1; j++)
	{
		scanf("%d%d", &u, &v);
		Insert(u, v); 
	}
	Dp(1);
	ans = max(y[1], n[1]);
	printf("%d\n", ans);
	return 0;
}