codeforces-862B Mahmoud and Ehab and the bipartiteness

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

很少做英文题，读题都花了不少时间……

比如” A cycle and a loop aren’t the same “

我理解成“循环和循环是不相同的”

？？？

后来查了维基百科才发现这里的loop是图论里的专用术语，中文可称作“环”——若一条边的两个顶点为同一顶点，则此边称作环

所以这句话的意思应该是“回路和环是不一样的”

题意：给出一个有n个顶点、n-1条边的树（在本题实际上就是图），求最多可以添加多少条边，使这个图仍然是二分图(图中不能有重边和环)

一开始的思路：先按二分图的做法用dfs进行染色，之后再遍历每一个顶点，查询该顶点和图中所有与其不相连的点是否异色，如果颜色不一样，则加一条边，最后输出一共加了多少条边

噼里啪啦一顿操作：

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

vector<int> G[100010];
int color[100010];//记录顶点的颜色（只有两种，1或-1）
int n,ans=0;

void ColorNode(int t,int c)
{
    color[t]=c;
    int i;
    for(i=0;i<G[t].size();++i)
        if(color[G[t][i]]==0)//如果未被染色
            ColorNode(G[t][i],-c);
}

bool FindVector(int a,int x)//判断顶点a是否与顶点x相连
{
    int i;
    for(i=0;i<G[a].size();++i)
        if(G[a][i]==x) return true;
    return false;
}

void AddEdge()
{
    int i,j;
    for(i=1;i<=n;++i)//遍历每一个顶点
    {
        for(j=1;j<=n;++j)
        {
            if(j==i) continue;
            if(!FindVector(i,j)&&color[i]!=color[j])//如果i,j不相连且j未被染色,则添加一条边
            {
                G[i].push_back(j);
                G[j].push_back(i);
                ++ans;
            }
        }
    }
}

void solve()
{
    int i;
    for(i=1;i<=n;++i)
        if(color[i]==0)
            ColorNode(i,1);//运用dfs进行染色
    AddEdge();
    printf("%d\n",ans);
}

int main()
{
    memset(color,0,sizeof(color));
    scanf("%d",&n);
    int i,u,v;
    for(i=0;i<n-1;++i)
    {
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);//无向图所以要反过来连接一次
    }
    solve();
    return 0;
}

TLE超时……

仔细一看题目，才发现最多共有10^5个点，按照上面AddEdge()函数里的写法，操作数已经远超过10^10，而2s的时限内最多只能有10^8乘一个常数的操作数

所以像这种纯暴力的方式实在是太慢了

此时我立刻意识到很有可能是通过某一个公式得出最后的答案的

推(xia)算(cai)了一会儿一个公式都没推(cai)出来，偷偷地看了看官方题解:

树本身是二分的，所以我们可以运行一个dfs将树分成2个集合（称为bicoloring），我们不能在同一集合中的任何2个节点之间添加边，我们可以在每2个在不同集合里的节点之间添加一个边，所以让左边的节点数为l，右侧的节点数为r，可以存在的最多边数为 l * r，但 n-1个边缘已经存在，所以要添加最多的边数是 l * r - (n - 1)

AC代码：

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

vector<int> G[100010];
int color[100010];//记录顶点的颜色（只有两种，1或-1）
int n;
long long a,b;

void ColorNode(int t,int c)
{
    color[t]=c;
    if(color[t]==1) ++a;//染色计数
    else ++b;
    int i;
    for(i=0;i<G[t].size();++i)
        if(color[G[t][i]]==0)//如果未被染色
            ColorNode(G[t][i],-c);
}

void solve()
{
    int i;
    for(i=1;i<=n;++i)
        if(color[i]==0)
            ColorNode(i,1);//运用dfs进行染色
    printf("%I64d\n",a*b-(n-1));//注意这里一定要用longlong！！！否则会wa
}

int main()
{
    memset(color,0,sizeof(color));
    scanf("%d",&n);
    int i,u,v;
    for(i=0;i<n-1;++i)
    {
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);//无向图所以要反过来连接一次
    }
    solve();
    return 0;
}