题目描述

二分图又称作二部图，是图论中的一种特殊模型。
设 G=(V,E) 是一个无向图，如果顶点 V 可分割为两个互不相交的子集 (A,B)，并且图中的每条边 (i,j) 所关联的两个顶点 i 和 j 分别属于这两个不同的顶点集 (i∈A,j∈B)，则称图 G 为一个二分图。
所有的树都是二分图。

给定一个 n 个节点的树。

树的节点编号为 1∼n。

请你为这棵树增加一些边，要求增边后的图形仍是二分图，并且不含重边和自环。

请问，最多可以增加多少条边。

输入格式

第一行包含整数 n，表示树的节点数量。

接下来 n−1 行，每行包含两个整数 a,b，表示节点 a 和节点 b 之间存在一条边。

输出格式

一个整数，表示可以增加的边的最大数量。

数据范围

前三个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤105，1≤a,b≤n。

样例

输入
5
1 2
2 3
3 4
4 5
输出
2

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010,M=N*2;
int s,h[N];
struct rec{
    int n,next;
}edge[M];
int d[N];
bool st[N];
int n,x,y;
void add(int a, int b)
{
    edge[++s].n = b, edge[s].next = h[a], h[a] = s ;
}
void dfs(int u)
{
    st[u]=true;
    if(d[u]%2==0) x++;
    else y++;
    for(int i=h[u];~i;i=edge[i].next)
    {
        int j=edge[i].n;
        if(st[j]) continue;
        d[j]=d[u]+1;
        dfs(j);
    }
}
int main()
{
    cin>>n;
    memset(h, -1, sizeof h);
    long long int cnt=0;
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        cnt++;
        add(a, b);add(b,a);
    }
    memset(d,-1,sizeof d);
    int l=0,r=0;
    for(int i=1;i<=n;i++)
    {
        if(!st[i])
        {
            d[i]=0;
            x=y=0;
            dfs(i);
            if(x>y) {int t=x;x=y;y=t;}
           if(l<r) l+=y,r+=x;
           else l+=x,r+=y;
        }
    }
    cout<<1ll*l*r-cnt<<endl;
    return 0;

}