\(\color{#0066ff}{题目描述}\)

给出n个点，n-1条边，求再最多再添加多少边使得二分图的性质成立

\(\color{#0066ff}{输入格式}\)

The first line of input contains an integer n — the number of nodes in the tree ( \(1<=n<=10^{5}\) ).

The next n−1 lines contain integers u and v ( \(1<=u,v<=n u≠v u≠v\) ) — the description of the edges of the tree.

It's guaranteed that the given graph is a tree.

\(\color{#0066ff}{输出格式}\)

Output one integer — the maximum number of edges that Mahmoud and Ehab can add to the tree while fulfilling the conditions.

\(\color{#0066ff}{输入样例}\)

51 22 33 44 5

\(\color{#0066ff}{输出样例}\)

2

\(\color{#0066ff}{题解}\)

先二分图染色（原图一定是二分图）

分别统计颜色为1和0的数量

开数组记录每个节点的度

显然du就是它已经连的和它颜色相反的节点的个数

因为要求做多连多少边，为了保证性质，只要颜色不同就行，所以剩下的总数-du个点都可以连边

每条边会被算两次，最后/2

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define _ 0#define LL long long#define Space putchar(' ')#define Enter putchar('\n')#define fuu(x,y,z) for(int x=(y),x##end=z;x<=x##end;x++)#define fu(x,y,z) for(int x=(y),x##end=z;x
            
             =x##end;x--)#define fd(x,y,z) for(int x=(y),x##end=z;x>x##end;x--)#define mem(x,y) memset(x,y,sizeof(x))#ifndef olinrinline char getc(){ static char buf[100001],*p1=buf,*p2=buf; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100001,stdin),p1==p2)? EOF:*p1++;}#else#define getc() getchar()#endiftemplate
             
              inline void in(T &x){ int f=1; char ch; x=0; while(!isdigit(ch=getc()))(ch=='-')&&(f=-f); while(isdigit(ch)) x=x*10+(ch^48),ch=getc(); x*=f;}struct node{ int to; node *nxt;};typedef node* nod; nod head[105005];int n;int col[105005],du[105050],num1,num0;LL ans;inline void dfs(int x,int c){ col[x]=c; for(nod i=head[x];i;i=i->nxt) { if(~col[i->to]) continue; dfs(i->to,c^1); } }inline void add(int from,int to){ nod t=new node(); t->to=to; t->nxt=head[from]; head[from]=t;}int main(){ int x,y; in(n); fuu(i,1,n) col[i]=-1; fuu(i,1,n-1) in(x),in(y),du[x]++,du[y]++,add(x,y),add(y,x); dfs(1,0); fuu(i,1,n) col[i]? num1++:num0++; fuu(i,1,n) ans+=(col[i]? num0:num1)-du[i]; printf("%lld\n",ans>>1); return ~~(0^_^0);}