题解：P6722 「MCOI-01」Village 村庄

· · 题解

题意

原图是一棵树，如果原图上两点的距离 dis(u,v)\ge k，那么在新图上这两点之间就会有一条边，求新图是不是二分图。

思路

一个图是二分图的充要条件是这个图中没有奇环。
容易看出，这棵树的直径的两个端点如果有连边（否则这个图就一定时是二分图），那么只要存在一个点，它与直径的两个端点都有连边，就存在一个奇环，此图就不是一个二分图。
因为如果所有点与直径的两个端点都没有连边， 于是我们就在找到直径的两个端点后，先以一个端点为根 O(n) 遍历整棵树，标记与该点在新图中有连边的所有点。再以另一个端点为根遍历一次，若此时找到一个点与直径的两个端点都有连边，那么这个图就不是二分图。
具体细节看代码吧！

代码

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int t,n,k,root,ans,maxn,dep[N],fa[N],b[N];
vector<pair<int,int>>a[N];
void dfs(int u,int x){
//x表示第几次遍历
    for(auto [v,w]:a[u]){
        if(v==fa[u])continue;
        fa[v]=u;
        dep[v]=dep[u]+w;
        if(x==1&&dep[v]>=k)b[v]=1;
        //第一次遍历，标记有连边的点
        if(x==2&&dep[v]>=k&&b[v])ans=1;
        //第二次遍历，寻找与两端点都有连边的点
        dfs(v,x);
        if(dep[v]>maxn){
            maxn=dep[v];
            root=v;
            //找直径
        }
    }
}
int main(){
    cin>>t;
    while(t--){
        memset(b,0,sizeof(b));
        ans=0;
        //初始化
        cin>>n>>k;
        for(int i=1;i<=n;++i)a[i].clear();
        for(int i=1;i<n;++i){
            int u,v,w;
            cin>>u>>v>>w;
            a[u].push_back(make_pair(v,w));
            a[v].push_back(make_pair(u,w));
            //存图
        }
        fa[1]=dep[1]=maxn=0;
        //记得请0
        dfs(1,0);
        fa[root]=dep[root]=maxn=0;
        dfs(root,1);
        fa[root]=dep[root]=maxn=0;
        dfs(root,2);
        if(!ans)cout<<"Yes\n";
        //如果没有有奇环，输出Yes
        else cout<<"Baka Chino\n";
        //否则输出Baka Chino
    }
    return 0;
}