problem

有一個n個節點n-1條邊組成的樹。
每個點看成一個人，連接u和v的邊看成是“中意關系”，即u和v兩個人都想和對方組隊。每個人希望組隊的對象有可能有多個。
一支隊伍由且僅由兩個人組成，并且如果u和v組隊了，那么u、v將不能和其他人再組成一支隊。
現在問你，這n個人最多能組成多少支隊伍。（允許某些人組不了隊）

Input

第一行輸入一個整數n,m(1<=n<=200000)
接下來n-1行，每行兩個整數u,v，表示u和v兩個人都想和對方組隊。
數據保證是一個合法的樹。

Output

輸出一個整數，表示最多能組成多少支隊伍。

Input

5
1 2
1 3
2 4
4 5

Output

2

Limitation

1s 256MB

Hint

一種可行的組隊方案：
1與3組隊
4與5組隊
最多組成2支隊

思路

基本的樹形DP
dp[rt][0]表示rt這個點不與任何一個兒子連邊，以k為根的子樹的最大匹配
dp[rt][1]表示rt這個點與某一個兒子連邊，以k為根的子樹的最大匹配

---

核心代碼

void dfs(int rt,int f) {int mi=n;if(G[rt].size()==1&&G[rt][0]==f){return ;}for(int i=0;i<G[rt].size();++i){int tt=G[rt][i];if(tt==f) continue;dfs(tt,rt);dp[rt][0]+=dp[tt][1];dp[rt][1]+=dp[tt][1];if(dp[tt][1]-dp[tt][0]<mi) mi=dp[tt][1]-dp[tt][0];}dp[rt][1]=dp[rt][1]-mi+1; }

代碼示例

#include<bits/stdc++.h> using namespace std; const int maxn=200010;int n;vector<int> G[maxn];int dp[maxn][2];void dfs(int rt,int f) {int mi=n;if(G[rt].size()==1&&G[rt][0]==f){return ;}for(int i=0;i<G[rt].size();++i){int tt=G[rt][i];if(tt==f) continue;dfs(tt,rt);dp[rt][0]+=dp[tt][1];dp[rt][1]+=dp[tt][1];if(dp[tt][1]-dp[tt][0]<mi) mi=dp[tt][1]-dp[tt][0];}dp[rt][1]=dp[rt][1]-mi+1; }int main() {ios::sync_with_stdio(false);cin>>n;int u,v;for(int i=1;i<n;++i){cin>>u>>v;G[u].push_back(v);G[v].push_back(u);}dfs(1,0);cout<<max(dp[1][0],dp[1][1])<<endl;return 0; }

總結

以上是生活随笔為你收集整理的17AHU排位赛2 E题（树上最大匹配，树形DP)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。