Step1 前置芝士：
如何证明一个图是二分图，又如何证明一个图不是二分图？
从定义入手： 二分图是一种不含有奇数条边环的图。
所以，对于此题，如果我们能确定新图中是否含有基环，我们就相应的可以确定这个数据合不合法。
Step2 从暴力开始
考虑如何暴力建新图？
如果$dis_{u, v} ge k$，那么在新图中就可以有连边呗。
所以，求出全源最短路，然后暴力建新图，最后判断是否为二分图就是我们的暴力做法了。
（~~感觉这个暴力也很麻烦的亚子，还不如继续推写正解(滑稽~~）
Step 3 考虑基环的性质
在一个基环上，我们考虑每个点的编号为$a_1, a_2, a_3$ ~ $a_m$。
其中$a_m$为编号最大的一个基环上的点, 令 $m > 3$。
假设基环上不存在一个点$a_p$, 满足$dis(a_1, a_p) ge k$ ^ $dis(a_p, a_m) ge k$，即不满足存在三元环的条件
不妨利用数学归纳法：
设一点$a_x$存在于基环上。
当 $x = 1$时，显然有 $dis(a_1, a_m) ge k$ ^ $dis(a_1, a_2) ge k$
当$x = 2$时，显然有 $dis(a_2, a_3) ge k$ ^ $dis(a_2, a_m) < k$
当$x = 2y(y ≠0)$时，有 $dis(a_{2y}, a_{2y+1}) ge k$ ^ $dis(a_{2y},a_1) < k$ ^ $dis(a_{2y}, a_m) < k$ $Rightarrow$ 可知，此时的$a_m$不能存在于基环中，显然不对。
（这里还要结合原图来看啊，建议大家结合样例来手摸。）
（基环）
那么，证明了图中存在三元环之后，~~我们来看看官方题解~~，看看三元环跟树的直径的关系。
假设图中1,2,3号点构成三元环。
那么，有$d + e ge k$, $d + f ge k$, $e + f ge k$.
令图中$a + b$为极大值，则 $4,5,6$为树的直径。
假设不存在一点到直径两端点可以构成三元环。
那么，令1号点等效于1,2,3号点。
为满足条件，我们有：
$d + c + a < k$, 配合前面的柿子：
$d + e ge k$
不等式基本原则，$a + c < e$
所以 $b + c + e > b + c + a + c > a + b$，此时$(2,6)$成为直径，不符合原图。
所以，三元环上一定有一点到直径的两端距离均大于$k$。于是，我们只要找出树的直径，然后判断是否有点到其两端的距离均$ge k$即可。如果存在，则原图存在基环，不成立。
#include <bits/stdc++.h> using namespace std; #define N 100010 template <class T> inline void read(T& a){ T x = 0, s = 1; char c = getchar(); while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); } a = x * s; return ; } struct node{ public: int v, w, next; public: node(int v = 0, int w = 0, int next = 0){ this -> v = v; this -> w = w; this -> next = next; return ; }// 为什么存个边要写得这么毒瘤？ 因为方便赋予初值啊 public: inline void clean(){ this -> v = 0; this -> next = 0; this -> w = 0; return ; } } t[N << 1]; int f[N]; int bian = 0; inline void add(int u, int v, int w){ t[++bian] = node(v, w, f[u]), f[u] = bian; t[++bian] = node(u, w, f[v]), f[v] = bian; return ; } int dis[N], dis1[N], dis2[N]; int s1, s2; int maxn = -666; int cur = 0; #define v t[i].v void dfs(int now, int father, int* dis){ // 用指针方便传入dis数组 if(dis[now] > maxn){ maxn = dis[now]; cur = now; } for(int i = f[now]; i; i = t[i].next){ if(v != father){ dis[v] = dis[now] + t[i].w; dfs(v, now, dis); } } return ; } #undef v inline void search(int x, int& y, int* dis){ // 找端点等各种操作 maxn = -666; cur = 0; dis[x] = 0; dfs(x, 0, dis); y = cur; return ; } inline void clean(){ // 不要忘记清空 for(int i = 1;i <= bian; i++) t[i].clean(); memset(f, 0, sizeof(f)); bian = 0; return ; } int main(){ int T; read(T); while(T--){ clean(); int n, k; read(n), read(k); s1 = 0, s2 = 0; for(int i = 1; i < n; i++){ int x, y, w; read(x), read(y), read(w); add(x, y, w); } search(1, s1, dis); search(s1, s2, dis1); // 找端点,顺便记录dis1 int temp = 0; search(s2, temp, dis2); // 多搜一次，找dis2 bool flag = 0; for(int i = 1;i <= n; i++) if(dis1[i] >= k && dis2[i] >= k) { flag = 1; break; } if(flag)puts("Baka Chino"); else puts("Yes"); } return 0; }