二分图练习

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

#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;
}