【题解-信息学奥赛一本通】2142：树边匹配
题目：2142：树边匹配
题目描述
给你一棵包含n个节点的树。
匹配一组边，其中每个节点最多是其中一条边的端点。匹配中最多有多少条边？
输入
第一行输入包含一个整数n：节点的数量。节点编号为1,2,…,n。然后有n−1行描述边。每行包含两个整数a和b：节点a和节点b之间有一条边。
输出
输出一个整数：最大边组数。
时空限制
1s / 64MB
样例输入
5 1 2 1 3 3 4 3 5样例输出
2提示】
样例解释：一个可能的匹配是 (1,2) 和 (3,4)。
数据范围：
1 ≤ n ≤ 2 × 10 5 1≤n≤2×10^51≤n≤2×105
1≤a,b≤n
代码1（DFS，超时）
#include<bits/stdc++.h>usingnamespacestd;typedefpair<int,int>PII;constintN=2e5+10;intn,x,y,ans,vissum;vector<PII>q;boolvis[N];voiddfs(intu,intsum){if(u==n-1){ans=max(ans,sum);return;}intx=q[u].first,y=q[u].second;if(!vis[x]&&!vis[y]){vis[x]=vis[y]=true;vissum+=2;dfs(u+1,sum+1);vis[x]=vis[y]=false;vissum-=2;}dfs(u+1,sum);}intmain(){cin>>n;for(inti=0;i<n-1;i++){cin>>x>>y;q.push_back({x,y});}dfs(0,0);cout<<ans;return0;}要想过，得用树形DP，等之后补