题目：Work Group

树形dp，设状态f[u][0/1] 表示以u为根节点，他的子树中选了0（偶数）1（奇数）个节点的最大价值，设x为他的一个儿子，显然f[u][1]=max(f[k][0]+f[u][1],f[k][1]+f[u][0]),f[u][0]=max(f[k][0]+f[u][0],f[k][1]+f[u][1])

最后再加上自身权值即可，答案为f[1][1]

代码：

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

const int N=2e5+5;

using namespace std;

struct graph

{

	int to,nxt;

	graph(int tt,int nn)

	{

		to=tt;nxt=nn;

	}

	graph(){

	}

}e[N];

int n,head[N],tot,a[N],vis[N];

long long dp[N][2];

void adde(int u,int v)

{

	++tot;

	e[tot]=graph(v,head[u]);

	head[u]=tot;

}

void dfs(int u)

{

	vis[u]=1;

	for(int i=head[u];i;i=e[i].nxt)

	{

		int k=e[i].to;

		if(vis[k])

		    continue;

		dfs(k);

		long long x=dp[u][0],y=dp[u][1];

		dp[u][1]=max(x+dp[k][1],y+dp[k][0]);

		dp[u][0]=max(x+dp[k][0],y+dp[k][1]);

	}

	dp[u][1]=max(dp[u][1],dp[u][0]+a[u]);

}

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

	{

		int v;

		scanf("%d %d",&v,&a[i]);

		dp[i][1]=-2e18;

		if(v!=-1)

		    adde(v,i);

	}

	dfs(1);

	printf("%lld\n",dp[1][1]);

	return 0;

}

巴特西

2022春每日一题：Day 24

题目：Work Group

最新文章

热门文章