P1352 沒有上司的舞會

題目#

某大學有 $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;
}