【题解-信息学奥赛一本通】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×1051≤a,b≤n代码1DFS超时#includebits/stdc.husingnamespacestd;typedefpairint,intPII;constintN2e510;intn,x,y,ans,vissum;vectorPIIq;boolvis[N];voiddfs(intu,intsum){if(un-1){ansmax(ans,sum);return;}intxq[u].first,yq[u].second;if(!vis[x]!vis[y]){vis[x]vis[y]true;vissum2;dfs(u1,sum1);vis[x]vis[y]false;vissum-2;}dfs(u1,sum);}intmain(){cinn;for(inti0;in-1;i){cinxy;q.push_back({x,y});}dfs(0,0);coutans;return0;}要想过得用树形DP等之后补