Codeforces 862B - Mahmoud and Ehab and the bipartiteness

862B - Mahmoud and Ehab and the bipartiteness

思路：先染色，然后找一种颜色dfs遍历每一个点求答案。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))const int N=1e6+5;
bool color[N]; 
vector<int>g[N];
int c=0;
int n;
ll ans=0;void dfs(int u,int v)
{color[v]=!color[u];if(color[v]==true)c++;for(int i=0;i<g[v].size();i++)if(g[v][i]!=u)dfs(v,g[v][i]);
}void DFS(int u,int v)
{if(color[v]==true)ans+=(n-c-g[v].size());for(int i=0;i<g[v].size();i++){if(g[v][i]!=u)DFS(v,g[v][i]);}
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int u,v;cin>>n;for(int i=0;i<n-1;i++){cin>>u>>v;g[u].pb(v);g[v].pb(u);}color[0]=false;dfs(0,1);DFS(0,1);cout<<ans<<endl;return 0;
}