# 中電會六月主題課程
# 進階動態規劃2
---
點名
回饋
---
## 樹
----
![](https://hackmd.io/_uploads/B1C3_mwSA.png =324x378)
* 對於任意兩個節點,洽有一條路徑的無向圖
* 無環的連通圖
* $n$個點,$n-1$條邊
----
### 名詞解釋
* 根節點
* 葉節點
* 父節點
* 祖先
* 子節點
* 子樹
----
### 存圖的方法
Adjacency list
![](https://hackmd.io/_uploads/B1C3_mwSA.png =324x378) ![image](https://hackmd.io/_uploads/HkQGhmDHC.png)
----
以編號1的節點為根,給2的父親、3的父親……
![image](https://hackmd.io/_uploads/BkWnlHYB0.png) ![image](https://hackmd.io/_uploads/H1Tf-rYH0.png)
----
```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);
}
```
----
給每一條邊的兩端節點編號
![image](https://hackmd.io/_uploads/ryLIQSFr0.png) ![image](https://hackmd.io/_uploads/rJNtQStrC.png)
----
```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);
}
```
----
### 圖的遍歷
以某種順序拜訪所有節點
![image](https://hackmd.io/_uploads/HJjY3YtHA.png =300x300)
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)
計算子樹大小
----
算過的不要再算
![image](https://hackmd.io/_uploads/Bkqgl5KH0.png =400x500)
黃色=藍色+綠色+紅色+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)
{"title":"中電會六月主題課程-進階動態規劃2","description":"點名","contributors":"[{\"id\":\"98ae9bd8-05ef-4e0a-b451-d465f67f398f\",\"add\":3196,\"del\":51}]"}