3132112_ac_422ms_1096k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <vector>
#include <algorithm>
#define Max(a,b) a>b?a:b
using namespace std;

int n;
vector <int> tree[6001];
vector <int> flor[6001];
int no, max;

void dfs(int v,int b)
{
	int i;

	flor[b].push_back(v);
	if(b>max)
		max = b;
	for(i = 0; i < tree[v].size(); i++)
		dfs(tree[v][i],b+1);
}

int num[6001][2];
int rate[6001];

int main()
{
	int i, j;
	int l, r, root;
	int mark[6001];
	
	scanf("%d",&n);
	memset(mark,0,sizeof(mark));
	for(i = 0; i < n; i++)
	{
		scanf("%d",&rate[i]);
	}
	for(i = 1; i < n; i++)
	{
		scanf("%d%d",&l,&r);
		l--;r--;
		mark[l]++;
		tree[r].push_back(l);
	}
	for(i = 0; i < n; i++)
	{
		if(mark[i]==0)
		{
			root = i;
			break;
		}
	}
	max = -1;
	dfs(root,0);
	memset(num,0,sizeof(num));
	for(i = max; i >= 0; i--)
	{
		for(j = 0; j < flor[i].size(); j++)
		{
			if(!tree[flor[i][j]].size())
			{
				num[flor[i][j]][0] = rate[flor[i][j]];
				num[flor[i][j]][1] = 0;
			}
			else
			{
				int v1, v0;
	
				v0 = rate[flor[i][j]];v1 = 0;
				for(int k = 0; k < tree[flor[i][j]].size(); k++)
				{
					v0 += num[tree[flor[i][j]][k]][1];
					v1 += Max(num[tree[flor[i][j]][k]][1],num[tree[flor[i][j]][k]][0]);
				}
				num[flor[i][j]][0] = v0;
				num[flor[i][j]][1] = v1;
			}
		}
	}
	max = Max(num[root][0],num[root][1]);
	printf("%d\n",max);
	return 0;
}