洛谷 P1352 没有上司的舞会 (树上不相邻点权和最大)

一颗树，选取不相邻的点，求最大点权值

因为当前结点选或不选后后效性，所以我们加一唯来取消后效性

$f[0][i]$ 表示以i为根的树且i不选的最大价值

$f[1][i]$ 表示以i为根的树且i选的最大价值

显然有

$f[1][i] = sum(f[0][son])$

$f[0][i] = sum(max(f[0][son], f[1][son]))$

#include<cstdio>

#include<vector>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 6123;

int f[2][MAXN], a[MAXN], b[MAXN], n;

vector<int> g[MAXN];

void dfs(int u)

{

	f[0][u] = 0;

	f[1][u] = a[u];

	if(!g[u].size()) return;

	REP(i, 0, g[u].size())

	{

		int v = g[u][i];

		dfs(v);

		f[1][u] += f[0][v];

		f[0][u] += max(f[0][v], f[1][v]);

	}

}

int main()

{

	scanf("%d", &n);

	REP(i, 1, n + 1) scanf("%d", &a[i]);

	int fa, son;

	while(~scanf("%d%d", &son, &fa) && fa)

	{

		g[fa].push_back(son);

		b[son] = 1;

	}

	REP(i, 1, n + 1)

		if(!b[i])

		{

			dfs(i);

			printf("%d\n", max(f[0][i], f[1][i]));

			break;

		}

	return 0;

}

巴特西

洛谷 P1352 没有上司的舞会 (树上不相邻点权和最大)

最新文章

热门文章