# 中電會六月主題課程 # 進階動態規劃2 --- 點名 回饋 --- ## 樹 ----  * 對於任意兩個節點，洽有一條路徑的無向圖 * 無環的連通圖 * $n$個點，$n-1$條邊 ---- ### 名詞解釋 * 根節點 * 葉節點 * 父節點 * 祖先 * 子節點 * 子樹 ---- ### 存圖的方法 Adjacency list   ---- 以編號1的節點為根，給2的父親、3的父親……   ---- ```cpp= int n; cin>>n; vector<vector<int>> g(n); for(int i=1;i<n;i++){ int f; cin>>f; f--; g[f].push_back(i); //g[i].push_back(f); } ``` ---- 給每一條邊的兩端節點編號   ---- ```cpp= int n; cin>>n; vector<vector<int>> g(n); for(int i=0;i<n-1;i++){ //有n-1條邊 int a,b; cin>>a>>b; a--; b--; g[a].push_back(b); g[b].push_back(a); } ``` ---- ### 圖的遍歷 以某種順序拜訪所有節點  DFS(深度優先搜索) ---- ```cpp= void dfs(int now,int pre){ //進入了now這個節點 for(int i:g[now]){ if(i==pre) continue; //不可以走回父節點 //準備進入i dfs(i,now); //離開了i，此時i的子樹都已經被訪問過了 } //準備離開pos } ``` --- ## 樹dp ---- ### [Subordinates](https://cses.fi/problemset/task/1674) 計算子樹大小 ---- 算過的不要再算  黃色=藍色+綠色+紅色+1 ---- 定義$sz[i]$為節點$i$的子樹大小(含自己)，$g[i]$為$i$的所有子節點 $$ sz[i]=1+\sum_{j\in g[i]} sz[j] $$ ---- ```cpp= #include<bits/stdc++.h> #define int long long using namespace std; vector<vector<int>> g; vector<int> sz; void dfs(int now){ for(int i:g[now]){ dfs(i); sz[now]+=sz[i]; } sz[now]++; } signed main(){ int n; cin>>n; g.resize(n); sz.resize(n); for(int i=1;i<n;i++){ int a; cin>>a; a--; g[a].push_back(i); } dfs(0); for(int i:sz){ cout<<i-1<<' '; } } ``` ---- ### [Tree Matching](https://cses.fi/problemset/task/1130/) ---- 定義$dp[0/1][i]$為$i$的子樹中，且$i$ (沒有/有) 選的情況下，最多有幾個Matching $$ dp[1][i]\geq dp[0][i] $$ ---- 若沒有拿$i$，$i$的所有子節點都可以選擇要拿或是不拿，由於拿了一定不會比較差，所以 $$ dp[0][i]=\sum_{j\in g[i]} dp[1][j] $$ 若有拿$i$，則表示必須有一個$j$是空著的，才能和$i$配對。計算哪一個$j$從要拿變成不拿所帶來的**代價**(我們叫他$mn$)最小，讓它空出來，再把$i$和$j$連接。 $$ dp[1][i]=dp[0][i]-mn+1 $$ ---- ```cpp= #include<bits/stdc++.h> #define int long long using namespace std; vector<vector<int>> g; vector<int> dp[2]; void dfs(int now,int pre){ int mn=1e18; for(int i:g[now]){ if(i==pre) continue; dfs(i,now); dp[0][now]+=dp[1][i]; mn=min(mn,dp[1][i]-dp[0][i]); } if(g[now].size()!=1||now==0){ //不是葉節點才可以考慮「拿」的可能 dp[1][now]=dp[0][now]-mn+1; } } signed main(){ int n; cin>>n; g.resize(n); dp[0].resize(n); dp[1].resize(n); for(int i=0;i<n-1;i++){ int a,b; cin>>a>>b; a--; b--; g[a].push_back(b); g[b].push_back(a); } dfs(0,0); cout<<dp[1][0]; } ``` --- ## [位元dp](https://hackmd.io/@tmting39/rJ7UjDvU3#%E4%BD%8D%E5%85%83dp)