P1352 没有上司的舞会 (树形dp)

链接：
luogu1352 没有上司的舞会

题目描述
某大学有 n个职员，编号为 1…n。

他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 ri
，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

输入格式

输入的第一行是一个整数 n。

第 2 到第 (n + 1) 行，每行一个整数，第 (i + 1) 行的整数表示 i号职员的快乐指数 ri。

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

输出格式

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

输入输出样例

输入 #1
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
输出 #1
5
说明/提示
数据规模与约定

对于 100% 的数据，保证 1<=n<=6 * 10^3 ，−128≤ri≤127，1≤l,k≤n，且给出的关系一定是一棵树。

Solution

经典的树的最大独立集问题变式，若设dp[i]为以i为根节点的子树的最大快乐指数，发现当前节点选或不选既可以影响自己的上司又可以影响自己的下属，具有后效性，故加一维，令dp[i][0]为以i为根节点的子树（且i不选）的最大快乐数，dp[i][1]表示以i为根节点的子树（且i选）的最大快乐数，故只要i确定了选或者不选，它的下属便清楚了选或者不选。

状态转移：
dp[x][0] += max(dp[v][0],dp[v][1]); （v为x的任意子节点）
dp[x][1] += dp[v][0];

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;
const int SZ = 6000 + 200;

struct zt
{
	int v,nxt;	
}node[SZ << 1];

int ans,n,temp,fist[SZ],nxt[SZ << 1],val[SZ];
int dp[SZ][3],in[SZ];

inline void build(int x,int y)
{
	node[ ++ temp].v = x;
	node[temp].nxt = fist[y];
	fist[y] = temp;
}
 
inline void dfs(int x)
{
	dp[x][1] += val[x];
	for(int i = fist[x];i != -1;i = node[i].nxt)
	{
		int v =	node[i].v;
		dfs(v);
		dp[x][0] += max(dp[v][0],dp[v][1]);
		dp[x][1] += dp[v][0];
	}
} 

int main()
{
	int a,b;
	scanf("%d",&n);
	memset(fist,-1,sizeof(fist));
	for(int i = 1;i <= n;i ++ )
		scanf("%d",&val[i]);
	for(int i = 1;i <= n;i ++ )
	{
		scanf("%d%d",&a,&b);
		if(a == 0 && b == 0) continue;
		in[a] ++ ;
		build(a,b);
	}
	int root;
	for(int i = 1;i <= n;i ++ )
	{
		if(in[i] == 0) 
		{
			root = i;
			break;
		}
	}
	dfs(root);
	ans = max(dp[root][1],dp[root][0]);
	printf("%d",ans);
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

2020.3.15