给你一棵树
让你进行切割
问你最多能切多少刀 使得每个连通分量size都是偶数
思路：首先 要是有奇数个节点的话 那么不管你怎么切割 都会有一个连通分量的size是奇数
所以只有偶数的情况才可能进行切割
切割的话 只要切割size为偶数的节点就行 把size为偶数的节点和他的父节点切开 就能保证连通分量的size为偶数
dfs一下就过了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
using namespace std;
const int maxn = 1e5+5;
vector<int> g[maxn];
bool vis[maxn];
int ans=0;
int dfs(int u);
int main()
{
int n,i,j,k;
scanf("%d",&n);
if(n%2)
{
printf("-1\n");
return 0;
}
memset(vis, false, sizeof(vis));
for(i=0;i<n-1;++i)
{
int a,b;
scanf("%d%d",&a,&b);
g[a].push_back(b);
g[b].push_back(a);
}
// dfs2(1,-1);
dfs(1);
cout << ans << endl;
}
int dfs(int u)
{
vis[u] = true;
int sum = 0;
for(int i=0;i<g[u].size();++i)
{
int v = g[u][i];
if(vis[v] == false)
{
sum+=dfs(v);
}
}
if(sum % 2 == 1 && u != 1)
ans ++;
return sum+1;
}
原文：https://www.cnblogs.com/mltang/p/9104561.html