什么是樹形DP？

概念：

給定一棵有N個節點的樹(通常是無根樹，也就是有N-1條無向邊)，我們可以任選一個節點為根節點，從而定義出每個節點的深度和每棵子樹的根，

在樹上設計動態規劃演算法時，一般就以節點從深到淺(子樹從小到大)的順序作為DP的“階段”，DP的狀態表示中，第一維通常是節點編號(代表以該節點為根的子樹)，大多數時候，我們采用遞回的方式實作樹形動態規劃，對于每個節點x，先遞回在它的每個子節點上進行DP，在回溯時，從子節點向節點x進行狀態轉移，

如何樹形DP？

樹形DP一般可以解決三類問題：
①最大獨立子集
②樹的重心
③樹的直徑
而這三類問題是樹形dp題的基礎，

最大獨立子集

最大獨立子集的定義是，對于一個樹形結構，所有的孩子和他們的父親存在排斥，也就是如果選取了某個節點，那么會導致不能選取這個節點的所有孩子節點，一般詢問是要求給出當前這顆樹的最大獨立子集的大小(被選擇的節點個數)，

最經典的莫過于這道題：

沒有上司的晚會

題目描述
Ural大學有N個職員，編號為1~N，他們有從屬關系，也就是說他們的關系就像一棵以校長為根的樹，父結點就是子結點的直接上司，每個職員有一個快樂指數，現在有個周年慶宴會，要求與會職員的快樂指數最大，但是，沒有職員愿和直接上司一起參加宴會，

輸入格式
第一行一個整數N，(1≤N≤6000)
接下來N行，第i+1行表示i號職員的快樂指數Ri，(-128≤Ri≤127)
接下來N-1行，每行輸入一對整數L,K，表示K是L的直接上司，
最后一行輸入0,0，

輸出格式
第1行：輸出最大的快樂指數，

樣例
樣例輸入
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
樣例輸出
5

分析

建立一個二維DP，第一維是節點的編號(也是子樹的根)，第二維是這個根節點參加與否，比如dp[3][1]表示以3號節點為子樹的根，當它參會時整棵子樹的快樂指數和；dp[3][0]表示以3號節點為子樹的根，當它不參會時整棵子樹的快樂指數和；這樣就可以滿足最優子結構的性質了，
d p [ i ] [ 0 ] = m a x ( d p [ k ] [ 0 ] , d p [ k ] [ 1 ] ) dp[i][0]=max(dp[k][0],dp[k][1]) dp[i][0]=max(dp[k][0],dp[k][1])

d p [ i ] [ 1 ] = d p [ k ] [ 0 ] + w [ i ] dp[i][1]=dp[k][0]+w[i] dp[i][1]=dp[k][0]+w[i]

注意：本題輸入的是一棵有根樹(制定了節點間的上下關系)，故我們需要先找出沒有上司的節點root作為根，DP的目標答案在 m a x ( d p [ r o o t ] [ 1 ] , d p [ r o o t ] [ 0 ] ) max(dp[root][1], dp[root][0]) max(dp[root][1],dp[root][0])中，
時間復雜度為O(n)，

#include<cstdio> 
#include<algorithm>
#include<cstring>
#include<vector>
#define max(x,y) x>y?x:y
using namespace std;
const int M=1e5+5;
int a[M];
vector<int> G[M];
bool flag[M];
int dp[M][5];
void read(int &x) {
	x = 0; 
	int f = 1;
	char s = getchar(); 
	while (s > '9' || s < '0') { 
		if (s == '-') f = -1; 
		s = getchar(); 
	}
	while (s >= '0' && s <= '9') { 
		x = (x << 3) + (x << 1) + (s - '0');
		s = getchar(); 
	}
	x *= f;
}//讀優
void dfs(int x){
	dp[x][0]=0,dp[x][1]=a[x];
	for(int i=0;i<G[x].size();i++){
		int id=G[x][i];
		dfs(id);
		dp[x][0]+=max(dp[id][0],dp[id][1]);
		dp[x][1]+=dp[id][0];
	}
}
int main(){
	int n;
	read(n);
	for(int i=1;i<=n;i++){
		read(a[i]);
	}
	for(int i=1;i<n;i++){
		int l,k;
		read(l),read(k);
		G[k].push_back(l);
		flag[l]=true;
	}
	for(int i=1;i<=n;i++){
		if(flag[i]==false){
			dfs(i);
			printf("%d",max(dp[i][1],dp[i][0]));
			return 0;
		}
	}
	return 0;
}
/*
7 
1 1 1 1 1 1 1
1 3 
2 3 
6 4 
7 4 
4 5 
3 5 
0 0 
5
*/