题目

某大学有 $n$ 个职员，编号为 $1\ldots n$。

他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 $r_i$，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

对于 $100\%$ 的数据，保证 $1\leq n \leq 6 \times 10^3$，$-128 \leq r_i\leq 127$，$1 \leq l, k \leq n$，且给出的关系一定是一棵树。

题解

设f[u][1/0]代表以u为子树选/不选u能获得的最大价值 然后分类即可

错误

1.add函数nxt写错 2.f[u][1]要加上r

代码

#include<bits/stdc++.h>

using namespace std;

const int N = 6e3 + 100; 

int read()
{
	int f = 1, x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}

	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return f * x;
}

int head[N], to[N], nxt[N], cnt = 1;
int n;
int r[N], in_edge[N], root;
int f[N][2];


void add(int x, int y)
{
	to[++cnt] = y;
	nxt[cnt] = head[x];
	head[x] = cnt;
}

void dfs(int u)
{
	for(int i = head[u]; i; i = nxt[i])
	{
		int v = to[i];
		dfs(v);
		f[u][1] += f[v][0];
		f[u][0] += max(f[v][0], f[v][1]);
	}
	f[u][1] += r[u];
	if(f[u][1] == 0 && f[u][0] == 0)
	{
		f[u][1] = r[u];
	}
	return;
}

int main()
{
	n = read();

	for(int i = 1;i <= n;i++)
	{
		r[i] = read();
	}
	int x, y;
	for(int i = 1;i < n;i++)
	{
		x = read(), y = read();
		add(y, x);
		in_edge[x] ++;
	}

	for(int i = 1;i <= n;i++)
	{
		if(in_edge[i] == 0)
		{
			root = i;
			break;
		}
	}

	dfs(root);

	printf("%d", max(f[root][1], f[root][0]));
	return 0;
}