# 樹狀DP
就是在樹上進行的DP(~~廢話~~)，因為樹有嚴格的層次關係，所以可以使用DP劃分出子問題，也就是當前的節點可透過子節點的解求出，即狀態轉移方程是由子節點推出父節點的。
遍歷方式 : 由於樹的特性，任兩個節點間只有一條路徑，所以通常利用深度優先搜索來遍歷。在推出狀態轉移方程後，DFS的過程如下 :

void dfs (int v, int fa) {
    for (int i=0; i<edge[v].size(); i++){
	    int son = edge[v][i];
	    if (son == fa) continue;
	    dfs (son, v);
	    update(v);  //每更新一個子節點，就更新一次
    }
    update(v);  //更新全部子節點後，再一次更新
}

**例題 : luogu P1352**
題意 : 某間大學有N個職員，他們之間有從屬關係，意旨他們之間就像一棵以校長為根的樹，父節點就是子節點的直接上司。現在有一場宴會，宴會每邀請一個職員就會增加一定的快樂指數$happy_i$(每個職員的快樂指數不一定相同)，但是呢，如果某個職員的直接上司來參加宴會，那麼該職員就不肯參加宴會了，試求宴會所能達到的最大快樂指數。

分析 : 每個職員有兩種狀態 : 不出席(編號為0)、出席(編號為1)，每個職員每種狀態的解由子節點決定，狀態轉移方程如下:
dp[v][0] = $\sum_{s}^{son}max(dp[s][0], dp[s][1])$
dp[v][1] = ($\sum_{s}^{son}dp[s][0])+happy_v$

**例題 : UVAOJ 1218**
題意 : 有n台機器形成樹狀結構，要求在某些機器上安裝伺服器，使得每台非伺服器的機器恰好與一台伺服器相連，求伺服器的最少數量。

分析 : 由於是樹狀結構，所以有嚴格的層次關係，可觀察層與層之間是否有關聯，透過觀察發現，如果某個節點是伺服器，那它的子節點可以是伺服器或未連接的狀態 ; 那如果節點是已連接的狀態，那子節點會有一台伺服器，而其他是已連接的狀態，最後一種可能是如果節點是未連接，那它的子節點都是已連接的狀態。
因此從上述說明，我們可以寫出以下的狀態轉移方程:

機器共有三種狀態:
0 代表 伺服器
1 代表 已連接
2 代表 未連接

dp[v][0] = $\sum_{s}^{son}max(dp[s][0], dp[s][2])$+1
dp[v][1] = $min(dp[i][0]+dp[s'][1])$ # s'是一個集合，s' = son - i
dp[v][2] = $\sum_{s}^{son}dp[s][1]$

----程式碼之後補上(最近被推甄跟專題弄得暈頭轉向)----