Mahmoud and Ehab and the bipartiteness | ACM

• 题目来源于：codeforces | Mahmoud and Ehab and the bipartiteness
• 背景知识：二分图 | ACM —— fenglinger

思路简述

• 既然是二分图，我们就需要从数据中将二分图构建出来，用染色法构建二分图

  • 所谓染色法，就是将每一个相连的点赋予不同的两种权值（例如0和1），遍历一遍相连的点，这些点就被分成了两个集合，权值为0和权值为1的集合。
• 至于计算要加多少条边，是没有必要的，在我们得出权值为0和权值为1的集合中分别有n，m个点时，我们可以求出此图的最大变数为n*m，我们用（n*m）- （n-1）即可得出想要的结果。

#include<stdio.h>
#include<vector>

using namespace std;
vector<long long> x[100005];
long long count[2];

void dfs(int a,int pa,int col)
{
    count[col]++;
    int len = x[a].size();
    for(int i = 0;i < len;i++)
    {
        if(x[a][i] != pa)
        dfs(x[a][i],a,!col);
    }
}
    
int main()
{
    int n;
    int a,b;
    while(~scanf("%d",&n))
    {
        for(int i = 1;i < n;i++)
        {
            scanf("%d %d",&a,&b);
            x[a].push_back(b);
            x[b].push_back(a);
        }
        dfs(1,0,0);
//        printf("%d\n",count[0]);
        printf("%lld\n",count[0]*count[1]-n+1);
 }
    return 0;
}

• 这一个图我改了好几个版本，一直wa在了第九个样例上面，改了一晚上，最后发现是我的数组少开了一个0；