题意:

给出一棵树,问最多去掉多少条边之后,剩下的连通分量的size都是偶数。

思路:

如果本来就是奇数个点,那么无论去掉多少条边都不可能成立的。

如果是偶数个点,就进行一次dfs,假设一个点的父亲是u,儿子是v,那么可以去掉(u,v)的条件就是v及其子树有偶数个点,任何一条这样的边都是可以去掉的。

所以一边dfs,一边统计答案就可以了。

代码:

 #include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
using namespace std;
const int N = 1e5 + ;
vector<int> g[N];
int ans = ;
int cnt[N];
int dfs(int u,int fa)
{
int ret = ;
for (int v:g[u])
{
if (v != fa)
{
int tmp = dfs(v,u);
if (tmp % == ) ans++;
ret += tmp;
}
}
return ret + ;
}
int main()
{
int n;
scanf("%d",&n);
if (n & )
{
printf("-1\n");
return ;
}
for (int i = ;i < n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
dfs(,-);
printf("%d\n",ans);
return ;
}
05-11 16:16
查看更多