树与二分图-2022RoboCom 世界机器人开发者大赛-本科组（省赛）_robocom编程

有点小遗憾，倒数第二题卡了半天最后也没写完，这道题只混了十五分，以2分之差没能冲进省一。

现在来看这题其实就是一个简单的二分图。我们只需要统计出两边的点数a和b，然后a b相乘减去（n - 1）就是答案了。

以样例来看左边共5个点，右边有2个点，二分图一共可以建10条边，题目已经帮我们建好了6条，所以我们最多只能建4条边。（个人建议：比赛的时候不要使用万能头。）

设 G=(V,E) 是一个无向图，如果顶点集合 V 可分割为两个互不相交的子集 (A,B)，并且每条边 (i,j)∈E 的两个端点 i 和 j 分别属于这两个不同的顶点子集，则称图 G 为一个二分图。

现在给定一棵树 T，要求选择树中两个没有边相连的结点 i 和 j，使得将无向边 (i,j) 加进 T 后能够构成二分图。你的任务是计算满足这个要求的选择方案有多少种。

输入格式:

输入第一行给出一个正整数 N (2≤N≤106)，表示树中结点的个数。

接下来 N−1 行，每行给出树中一条边的两端结点编号，以空格分隔。结点编号从 1 开始。题目保证输入给出的是一棵树中所有的边。

输出格式:

在一行中输出方案数。注意：连接 (1,2) 和 (2,1) 视作同一个方案。

输入样例:

7
1 2
2 3
2 4
2 5
2 6
4 7

输出样例:

4

代码长度限制

16 KB

Java (javac)

时间限制

1300 ms

内存限制

512 MB

其他编译器

时间限制

500 ms

内存限制

64 MB

#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std ;
typedef long long LL ;
const int N = 1000010 , M = N * 2 ;
LL n , x , y ;//因为数据范围1e6 相乘会爆int
int h[N] , e[M] , ne[M] , idx , col[N] ;//数组模拟链表来存储边
 
void add(int a , int b)
{
    e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ;
}
void dfs(int u , int c)
{
    col[u] = c ;
    if(c == 1) x ++ ;
    else y ++ ;
    
    for(int i = h[u] ; ~i ; i = ne[i])
    {
        int j = e[i] ;
        if(!col[j]) dfs(j , 3 - c) ;//没有染色的点染色
    }
    
    return ;
}
 
int main()
{
    cin >> n ;
    memset(h , -1 , sizeof h) ;
    for(int i = 1 ; i <= n - 1 ; i ++)
    {
        int a , b ;
        cin >> a >> b ;
        add(a , b) , add(b , a) ;//无向边
    }
    
    for(int i = 1 ; i <= n ; i ++)
        if(!col[i]) dfs(i , 1) ;//左边标记为1，右边标记为2
    
    cout << x * y - n + 1 << endl ;
    return 0 ;
}