---
tags: CSES題解
---

CSES Problem Set — Tree Matching 題解
===

題目
---
給一顆有$n$個點的樹。
定義匹配是對的集合，其中每個節點最多是其中一對的端點。匹配中對的最大數量是多少？

### 輸入
第一行輸入包含一個整數$n$ : 節點的數量。這些節點編號為$1,2,\ldots,n$。
接下來有$n-1$描述邊。每一行包含兩個整數$a$和$b$ : 點$a$和$b$間有一條邊。

### 輸出
輸出匹配中最多的對的數量

想法 : 樹形dp
---
由於樹上無環，我們可以透過子節點上的資訊轉移到父節點，根據題意如果父節點與子節點為一對，子節點就不能跟其子節點一對。

我們可以定義狀態$dp(x,0)$表示x節點不與其子節點成對的最大匹配對數，$dp(x,1)$表示x節點與子節點成對的最大匹配對數。

其中$dp(x,0)$可由其子節點的0狀態和1狀態取大值轉移，因為不與子節點成對時，子節點就不會影響父節點的匹配關係。

而$dp(x,1)$則要處理完整顆子樹後，再枚舉每個子節點與他成對取最大值，轉移方式見範例程式碼。

範例程式碼
---

#include<bits/stdc++.h>
#define int long long
using namespace std;

int cnt=1;
vector<int> Head(200500,0);
vector<int> Next(400500);
vector<int> To(400500);
vector<vector<int>> dp(200500,vector<int>(2,0));
void addEdge(int u,int v){
    Next[cnt]=Head[u];
    To[cnt]=v;
    Head[u]=cnt++;
}
/*************鍊式前向星建圖****************/

void dfs(int u,int par){
    for(int e=Head[u];e;e=Next[e]){
        int v=To[e];
        if(v!=par){
            dfs(v,u);
            //子節點不影響父節點成對
            //所以取大者轉移
            dp[u][0]+=max(dp[v][1],dp[v][0]);
        }
    }

    //枚舉每個子節點取最大
    for(int e=Head[u];e;e=Next[e]){
        int v=To[e];
        if(v!=par){
            //由於dp[u][0]可能由dp[v][1]或dp[v][0]轉移
            //我們不能確定從哪個轉移
            //所以減去max(dp[v][1],dp[v][0])
            //再加上dp[v][0]，因為若與子節點成對，子節點不能和其子節點成對
            //最後加上1，和子節點成對了，所以對數+1
            dp[u][1]=max(dp[u][1],dp[u][0]-max(dp[v][1],dp[v][0])+dp[v][0]+1);
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        addEdge(a,b);
        addEdge(b,a);
    }
    dfs(1,1);
    cout<<max(dp[1][0],dp[1][1]);
    return 0;
}