没有上司的舞会

题目

题目链接

题解

树形dp。

状态定义比较固定。f[i][0]表示以i为根的子树中，不选i时的最大值或最小值，f[i][1]表示以i为根的子树中，选i时的最大值或最小值。状态转移一般需要根据题目判断，只要用子节点的f信息合理更新f[i][0]和f[i][1]即可。

主要提及邻接表。

代码

#include
using namespace std;
const int N = 6005;

int n, idx, e[N  a >> b;	
		st[a] = true;
		add(b, a); // 父节点指向子节点 
	}
	
	int root = 1; // 自己确定根节点 
	while(st[root]) root ++;
	
	dfs(root);
	
	cout