题解
观察一个二分图会发现
- 同一组的节点不直接相连
- 二分图能够建立的最多的边等于 \(n*m\)
code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll> G[100005];
ll depth[100005]={0};
ll odd=0,even=0;
void dfs(ll now,ll fa)
{
if(depth[now]&1) odd++;
else even++;
for(auto next:G[now])
{
if(next==fa) continue;
depth[next]=depth[now]+1;
dfs(next,now);
}
}
int main()
{
ll n;
cin>>n;
for(ll i=1;i<n;i++)
{
ll x,y;
cin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
depth[1]=1;
dfs(1,-1);
cout<<odd*even-n+1;
return 0;
}
标签:bipartiteness,ll,back,dfs,next,depth,Mahmoud,Ehab,now
From: https://www.cnblogs.com/pure4knowledge/p/18196695