洛谷 P1352 没有上司的舞会

树形动规入门题

先放题面

这是一道非常简单的树形动规入门题，思路也很简单

摘取题意可知，一个人不愿意与自己的直接上司同时参加舞会，也就是相当于一个人不能与自己直接下属及直接上司同时参加舞会，继续化简就是每个点不会与和自己直接相连的点同时被选中说白了就是

最大独立集问题

那么我们直接看代码说话咯

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cctype>

#define gc() getchar()

#define ll long long

#define maxn 6005

using namespace std;

inline ll read(){   //快读不多解释

	ll a=0;char p=gc();int f=0;

	while(!isdigit(p)){f|=(p=='-');p=gc();}

	while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}

	return f?-a:a;

}

struct ahaha{   //邻接表存边

	int to,next;

}e[maxn*2];

int n,head[maxn],sz,a[maxn];

ll f[maxn][2];   //f[i][0]表示第i个点未被选中的最大值，f[i][1]表示第i个点被选中的最大值

inline void add(int u,int v){  //添加边的操作

	e[sz].to=v;e[sz].next=head[u];head[u]=sz++;

}

void dfs(int u,int fa){    //核心深搜

	for(int i=head[u];~i;i=e[i].next){   //遍历这个点的所有儿子

		int v=e[i].to;if(v==fa)continue;   //防止循环回去

		dfs(v,u);

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

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

	}

}

int main(){memset(head,-1,sizeof head);   //head数组置为-1方便判回操作

	n=read();

	for(int i=1;i<=n;++i){a[i]=read();f[i][1]=a[i];}  //若一个点被选中，则至少加上它自己的“快乐指数”

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

		int x=read(),y=read();

		add(x,y);add(y,x);

	}

	dfs(1,0);  //以1为根节点（这道题并没有交代根节点，所以以1为根节点）

	printf("%lld",max(f[1][0],f[1][1]));

	return 0;

}