树上最大独立集可以算是一种树形DP。

最大独立集（MIS,maximum independent set）

是 NP 困难独立集是指图 G 中两两互不相邻的顶点构成的集合。任意有关图中团的性质都能很自然的转述成独立集的性质。一般而言，寻找图的最大团的，从而寻找图的最大独立集也是 N-P 困难的。但是，对于二部图的情形，有多项式时间算法找出图的最大独立集。
简单说，就是从图中找出最多的点，使得他们都互不相邻。既然是树形DP，大多数情况都是在树上跑DP。但是实际情况中，点都是有点权的。所以又是最大权独立集。

例题

有一棵n个点的树，点有点权，求一个点的独立集，使独立集的点权之和最大。
简单的不能再简单，直观的不能再直观。

Slove

1. 设r[i]为i的点权，d[i]为以i为根节点的MIS，s[i]为i的所有儿子节点的d[]的总和，gs[i]为i的所有孙子节点的d[]总和。d[i]=max(r[i]+gs[t],s[t]);
2. 以一号节点为根节点，进行dfs，用dfn[]记录dfs序。
3. 从dfn[]的倒序枚举，进行更新。答案就是d[1]。

Code

int r[],d[],s[],gs[],fa[],dfn[];
int sum;  //dfn[]的数组大小
void dfs(int s,int f){
	fa[s]=f;
	dfn[++sum]=s;
	for(int i=first[s];i!=-1;i=next[i]) if(to[i]!=f) dfs(to[i],s);
}
void MIS(){
	for(int i=n;i>=1;i--){
		int t=dfn[i];
		d[t]=max(r[t]+gs[t],s[t]);
		s[fa[t]]+=d[t];
		gs[fa[fa[t]]]+=d[t];
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) first[i]=-1,scanf("%d",&r[i]);
	// 建图 //这里我用的是邻接表。
	dfs(1,0);
	MIS();
	printf("%d",d[1]);
	return 0;
}

相关题目

P1352 没有上司的舞会