Cut 'em all!

题意:求删除了边之后,剩下的每一块联通块他的点数都为偶数,求删除的边最多能是多少。

题解:如果n为奇数,直接返回-1,因为不可能成立。如果n为偶数,随意找一个点DFS建树记录下他的子孙+本身的个数。然后再DFS一下,对于每一个点,他的个数为偶数,就把他与父节点的边隔断, cnt++。 最后cnt就是答案。

代码:

 #include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9+;
const int N = 1e5+;
vector<int> son[N];
int ans = ;
int cnt[N];
void dfs(int o, int u){
cnt[u] = ;
for(int i = ; i < son[u].size(); i++){
int v = son[u][i];
if(o == v) continue;
dfs(u,v);
cnt[u] += cnt[v];
}
}
void dfs2(int o, int u){
if(cnt[u]% == ) ans++;
for(int i = ; i < son[u].size(); i++){
int v = son[u][i];
if(o == v) continue;
dfs2(u,v);
} }
int main(){
///Fopen;
int n, u, v;
scanf("%d", &n);
for(int i = ; i < n; i++){
scanf("%d%d", &u, &v);
son[u].pb(v);
son[v].pb(u);
cnt[u]++;
cnt[v]++;
}
if(n&){
printf("-1");
return ;
}
dfs(,);
for(int i = ; i < son[].size(); i++)
dfs2(,son[][i]);
printf("%d", ans);
return ;
}

最新文章

  1. [转]linux awk命令详解
  2. springMVC导出 CSV案例
  3. UILocalNotification本地通知
  4. 一个漂亮的DIV搜索条
  5. eclipse 将文件夹作为sourcefolder
  6. kali linux /etc/apt/source.list
  7. How Do I Declare A Block in Objective-C? [备忘]
  8. 《java入门第一季》之面向对象(内部类到底在哪里?)
  9. 关于redis服务无法启动问题
  10. python语言程序设计3
  11. Linux内核的启动过程分析
  12. DD-WRT自定义脚本更新花生壳DDNS
  13. shell批量杀进程
  14. 洛咕 P2494 [SDOI2011]保密
  15. 优秀web资源
  16. Hadoop的体系结构之HDFS的体系结构
  17. 24UDP通信
  18. Json&XML比较
  19. android4.0 4.1 4.2 4.3 4.4新特性
  20. Caffe学习系列(8):solver,train_val.prototxt,deploy.prototxt及其配置

热门文章

  1. go单元测试
  2. Python基础总结之认识lambda函数、map函数、filter() 函数。第十二天开始(新手可相互督促)
  3. spring学习笔记之---bean属性注入
  4. kubernetes CRD开发指南
  5. idea使用大全(加载mysql驱动)
  6. Python基础总结之初步认识---class类的继承(下)。第十五天开始(新手可相互督促
  7. 搞定java String校招面试题
  8. resolv.conf文件配置相关的案例
  9. idea中pom如何加载jar包依赖
  10. Linux面试题总结