<题目链接>
题目大意：
给出一个有n个点的二分图和n-1条边，问现在最多可以添加多少条边使得这个图中不存在自环，重边，并且此图还是一个二分图。
解题分析：
此题不难想到，假设二分图点集数量分别为x,y,添加最多的边数，无非就是x*y-(n-1)，于是，我们利用dfs对所有点进行染色，进而将其划分为两个集合。
#include <bits/stdc++.h>
using namespace std; const int N = 1e5+;
typedef long long ll;
int n,num1,num2;
vector<int>G[N];
int vis[N]; void dfs(int u,int id){
if(id&)num1++;
else num2++;
vis[u]=;
for(auto v:G[u]){
if(!vis[v])dfs(v,id^);
}
}
int main(){
cin>>n;
for(int i=;i<n;i++){
int u,v;scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(,);
ll ans=(ll)num1*(ll)num2-n+;
printf("%lld\n",ans);
}
2018-08-15