1212: 年会(树形dp)

参考代码:

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int to;
	int next;
}mp[100005];
int head[100005];
int cnt=0;
void add(int a,int b)
{
	mp[++cnt].to=b;
	mp[cnt].next=head[a];
	head[a]=cnt;
}
int a[100005];
int dp[100005][5];
void dfs(int u,int fa)
{
	for(int i=head[u];i;i=mp[i].next)
	{
		int v;
		v=mp[i].to;
		if(v!=fa)
		{
			dfs(v,u);
		}
	}
	dp[fa][0]+=max(dp[u][1],dp[u][0]);//父节点不被邀请时,子节点可被邀请也可不被邀请
	dp[fa][1]+=dp[u][0];//父节点被邀请子节点不能被邀请
	
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>dp[i][1];
	}
	for(int i=1;i<n;i++)
	{
		int a,b;
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	dfs(1,0);
	int ans=0;
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=1;j++)
		{
			ans=max(ans,dp[i][j]);
		}
	}
	cout<<ans;
	return 0;
}