Codeforces 862B Mahmoud and Ehab and the bipartiteness

题目链接:http://codeforces.com/problemset/problem/862/B

题意:给你一棵树,问最多加多少条边仍然是二分图。

思路:对树进行黑白染色,划分集合,二分图就是同一集合的点不能连接,统计一下两个集合的数目,乘一下减去原有的n-1条边就是答案了...定义掌握的还不行..

#include <bits/stdc++.h>
using namespace std;
const int maxn=100005;
int n;
vector<int>G[maxn];
int cnt[2];
void dfs(int u,int f,int color){
    cnt[color]++;
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==f) continue;
        dfs(v,u,1-color);
    }
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<n;i++){
        int u,v;scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0,0);
    printf("%lld\n",(long long)cnt[0]*cnt[1]-(n-1));
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注