Robocom-5 树与二分图_robocom 树与二分图

PTA | 程序设计类实验辅助教学平台

dfs给两集合涂色

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+7,inf=0x3f3f3f3f;
int n,head[N],cnt,col[N];
struct nn{
    int v,nex;
}e[N<<1];
void adde(int x,int y){e[++cnt]={y,head[x]};head[x]=cnt;}
void dfs(int u ,int fa){//2个集合涂色
    if(!col[u])col[u]=1;
    for(int i=head[u];i;i=e[i].nex){
        int v=e[i].v;
        if(v==fa)continue;
        col[v]=(col[u]==1)?-1:1;
        dfs(v,u);
    }
}
int main () { 
    int x,y;
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        adde(x,y);
        adde(y,x);
    }
    dfs(1,0);
    x=0;y=0;
    for(int i=1;i<=n;i++){
        if(col[i]==1)x++;
        else y++;
    }
    ll ans=1LL*x*y-(n-1);
    printf("%lld\n",ans);
}