CF862B Mahmoud and Ehab and the bipartiteness(二分图的性质）-Code:

constexpr int N=2e5+5,mod=1e9+7;

int n;
int h[N],e[N],ne[N],idx;
int color[N],cnt[4];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int u,int c)
{
    color[u]=c;
    cnt[c]++;
  for(int i=h[u];~i;i=ne[i])
  {
    if(!color[e[i]]) dfs(e[i],3-c);
  }
  
}

void solve()
{ 
   cin>>n;
    memset(h,-1,sizeof h);
   for(int i=1;i<=n;i++)
   {
    int a,b;cin>>a>>b;
    add(a,b),add(b,a);
   }  
    dfs(1,1);
   int sum=cnt[1]*cnt[2];
   cout<<sum-n+1;
}