题意

https://vjudge.net/problem/CodeForces-862B

给出n个点,n-1条边,求再最多再添加多少边使得二分图的性质成立

思路

因为题目是求的最多添加多少边,所以可以对树01染色,然后让每个0点连上所有的黑点,一共有0的个数*1的个数条边。再减去树的n-1条边即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=200005;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
vector<int> g[N];
ll col[N],num[2];
void dfs(int u,int fa)
{
for(int v:g[u])
{
if(v==fa)
continue;
col[v]=col[u]^1;
num[col[v]]++;
dfs(v,u);
}
}
int main()
{
std::ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=1; i<n; i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
num[0]++;
col[1]=0;
dfs(1,0);
cout<<num[0]*num[1]-(n-1)<<endl;
return 0;
}

  

最新文章

  1. Linux终端杀手、程序员利器-Tmux
  2. WCF Throttling 限流的三道闸口
  3. 开发板ping不通主机和虚拟机的看过来(转载)!
  4. Error : Must specify a primary resource (JAR or python or R file)
  5. sudo权限添加 和 rpm、deb之名词解释
  6. matlab语言基础
  7. uploadify 下载组件使用技巧和在线预览 word,excel,ppt,pdf的方案
  8. 易元平台使用-MVC体会
  9. access 2007 vba 开发中学到的知识(一)
  10. MYSQL alter procedure alter function 它们只可以更改过程的特性,不可以更改过程的逻辑。
  11. js延迟函数
  12. python爬虫解决编码问题
  13. 关于Python中迭代器的作用
  14. 结合源码浅谈Spring容器与其子容器Spring MVC 冲突问题
  15. php导出excel不使用科学计数法
  16. 解决IE8下opacity属性失效问题,无法隐藏元素
  17. [Laravel] Laravel的基本数据库操作部分
  18. Linux之V4L2基础编程【转】
  19. [Java] Apache Ant 构建基础教程
  20. week5 03 continus loading news

热门文章

  1. Password Management:Hardcoded Password 密码管理:硬编码密码
  2. Kubernetes行业调研报告:多集群、多云部署成企业首选策略
  3. 【Leetcode 做题学算法周刊】第五期
  4. seaborn画出的一些好看的图片
  5. UML简单介绍—类图这么看就懂了
  6. JavaScript 之 对象属性的特性 和defineProperty方法
  7. webpack-dev-server config.js Cannot find module
  8. [20191127]表 full Hash Value的计算.txt
  9. mongodb使用_遍历列表中的元素,作为变量,循环修改mongodb中的字段
  10. application context not configured for this file于spring框架使用中的原因