2022 RoboCom 世界机器人开发者大赛-本科组（省赛）

RC-u5 树与二分图

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

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

输入格式:

输入第一行给出一个正整数 $N$ ($2\le N\le 10^6$)，表示树中结点的个数。

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

输出格式:

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

输入样例:

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

输出样例:

4

已知树一定是二分图，先dfs出树中每个节点到根节点的距离，根据距离将树中每个节点分成两类，比如给树染成红白两色，只考虑从红色开始的节点连边，红色可以向所有除了临点之外的白色点连边，暴力即可。

#include<bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<":"<<x<<endl
#define ll long long 

const int N = 2e6+10;
int h[N],e[N],ne[N],idx;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int n;
int dist[N];

void dfs(int u,int fa,int len){
    dist[u] = len;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==fa)continue;
        if(dist[j] == 0){
            dfs(j,u,len+1);
        }        
    }
}
int din[N];
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);
        din[a]++;
        din[b]++;
    }
    dfs(1,-1,0);
    ll even,odd,m;
    even = odd = m = 0;
    for(int i=1;i<=n;i++){
    	if(dist[i]%2==0){
    		even ++;
    		m+=din[i];
    	}
    }
    odd = n - even;
    cout<<odd*even-m<<endl;
    return 0;
}