CodeForces 982 C Cut 'em all!
2024-09-01 08:02:37
题意:求删除了边之后,剩下的每一块联通块他的点数都为偶数,求删除的边最多能是多少。
题解:如果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 ;
}
最新文章
- [转]linux awk命令详解
- springMVC导出 CSV案例
- UILocalNotification本地通知
- 一个漂亮的DIV搜索条
- eclipse 将文件夹作为sourcefolder
- kali linux /etc/apt/source.list
- How Do I Declare A Block in Objective-C? [备忘]
- 《java入门第一季》之面向对象(内部类到底在哪里?)
- 关于redis服务无法启动问题
- python语言程序设计3
- Linux内核的启动过程分析
- DD-WRT自定义脚本更新花生壳DDNS
- shell批量杀进程
- 洛咕 P2494 [SDOI2011]保密
- 优秀web资源
- Hadoop的体系结构之HDFS的体系结构
- 24UDP通信
- Json&XML比较
- android4.0 4.1 4.2 4.3 4.4新特性
- Caffe学习系列(8):solver,train_val.prototxt,deploy.prototxt及其配置