题解 P1352【没有上司的舞会】

P1352 没有上司的舞会

本蒟蒻的第一篇题解~

题面

题目描述

某大学有$n$个职员，编号为$1\cdots n$。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数$r_i$，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

输入格式

输入的第一行是一个整数$n$。$(1\le n\le 6000)$

第$2$到第$(n+1)$行，第$(i+1)$行的整数表示$i$号职员的快乐指数$r_i$。$(-128\le r_i\le 127)$

第$(n+2)$到第$2n$行，每行输入一对整数$l,k$,代表$k$是$l$的直接上司。

输出格式

输出一行一个整数代表最大的快乐指数。

解析

我刚学树形dp写对了一道题就来写题解

定义数组$f[maxn+1][2]$，其中$f[x][0]$表示以$x$为子树树根的子树在$x$不参加舞会时的最大快乐值，$f[x][1]$表示以$x$为子树树根的子树在$x$参加舞会时的最大快乐值。

根据题目描述可知，上司去了，下属一定不去；上司不去，下属可去可不去。则可得

$$f[x][1]=r[x]+\sum _{y\in x\mathrm{的}\mathrm{儿}\mathrm{子}}f[y][0]$$

即将每个下属不去时得到的快乐值累加再加上$x$去时得到的快乐值

$$f[x][0]=\sum _{y\in x\mathrm{的}\mathrm{儿}\mathrm{子}}max(f[y][0],f[y][1])$$

即将每个下属去或不去得到的快乐值中选最大值再累加

得到了状态转移方程，只要找到根$root$，直接$dfs(root)$即可。

其余详见代码。

Code

我知道你们只看这个

#include<bits/stdc++.h>
using namespace std;

int r[6001],head[6001],f[6001][2],cnt;//f数组的意义如上所述

struct Edge{		//前向星存图
	int to;
	int next;
}edge[6001];

void add_edge(int from,int to)	//连边
{
	edge[++cnt].next=head[from];
	edge[cnt].to=to;
	head[from]=cnt;
}

bool not_root[6001];	//为了找根而开辟的数组，not_root[x]=1表示x不是根

void dfs(int x)			//树形dp
{
	f[x][1]=r[x];		//f[x][1]初始设置为自己的快乐值
	f[x][0]=0;			//f[x][0]初始设置为0
	for(int i=head[x];i;i=edge[i].next){	//遍历x的连边
		dfs(edge[i].to);	//先计算儿子
		f[x][1]+=f[edge[i].to][0];
		f[x][0]+=max(f[edge[i].to][0],f[edge[i].to][1]);
        //这两个式子的意义如上所述
	}
}

int main()
{
	int n,i,l,k,root;
	cin>>n;
	for(i=1;i<=n;i++)cin>>r[i];		//输入
	for(i=1;i<=n-1;i++){
		cin>>l>>k;
		add_edge(k,l);				//单向连边，只连父亲到儿子即可
		not_root[l]=1;				//是儿子肯定不是根
	}
	for(i=1;i<=n;i++)
		if(!not_root[i]){			//找根
			root=i;
			break;
		}
	dfs(root);						//从根开始dp
	cout<<max(f[root][0],f[root][1]);	//输出根节点去和不去时所得快乐值中的最大值
	return 0;
}