Jisoo

如果这玩意成不了二分图，肯定有环，而且还是肯定有一个三元环

如果一个点到两个点的距离$>k$那么这两个点之间的距离一定大于k

那么我们只要确定存不存在这样的三元组就可以了

怎么确定呢

画图可得，如果有三元环，那么这个三元环一定会存在一种包括两端点的情况

然后就显然我们要找直径，检查每一个点到这两端点的距离

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,k;
int head[100005];
struct e{
    int f;
    int to;
    int ne;
}ed[200005];
int t;
int p;
int x,y,z;
void add(int f,int t,int v){
    p++;
    ed[p].to=t;
    ed[p].ne=head[f];
    ed[p].f=v;
    head[f]=p;
}
int dis[100005][2];
void dfs(int xx,int f,int diss){
//  cout<<x<<" "<<f<<endl;
    for(int i=head[xx];i;i=ed[i].ne){
        if(ed[i].to==f) continue;
        dis[ed[i].to][diss]=dis[xx][diss]+ed[i].f;
    //  cout<<ed[i].f<<endl;
        if(dis[ed[i].to][diss]>x){
            x=dis[ed[i].to][diss];
            y=ed[i].to;
        }
        dfs(ed[i].to,xx,diss);
    }
}
int x1,x2;
int main(){
    scanf("%d",&t);
    while(t--){
        memset(head,0,sizeof(head));
        p=0;
        scanf("%d%d",&n,&k);
        for(int i=1;i<n;++i){
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
            add(y,x,z); 
        }
        x=0;
        dis[1][0]=0;
        y=1;
        dfs(1,0,0);
        x1=y;
        x=0;
        dis[x1][0]=0;
        dfs(x1,0,0);
        x2=y;
        x=0;
        dis[x2][1]=0;
        dfs(x2,0,1);
        int f=1;
        for(int i=1;i<=n;++i){
            if(dis[i][0]>=k&&dis[i][1]>=k){
                f=0;
                break;
            }
        }
        if(f){
            printf("Yesn");
        }else{
            printf("Baka Chinon");
        }
    }
    return 0;
}