二分图练习

对于二分图我们可以用染色法

#include<bits/stdc++.h>
using namespace std;#define int long long
const int N = 2e6+5;
int e[N],ne[N],h[N],idx = 0;
int colo[N];
int num = 0;void add(int x,int y){e[++idx] = y;ne[idx] = h[x];h[x] = idx;
}
void dfs(int nod,int c){colo[nod] = c;if(c==1) num++;for(int i = h[nod];i!=-1;i = ne[i]){int to = e[i];if(!colo[to]){dfs(to,3-c);//cout << nod << endl;}//cout << nod<< " sb " << endl;}
}
signed main(){int n;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);}dfs(1,1);cout << (n-num)*num-(n-1);return 0;
}