32pts求调
查看原帖
32pts求调
1145602
dongzhen楼主2025/1/20 15:57
#include <bits/stdc++.h>
#define lnt long long
#define inf 0x3f3f3f3f
using namespace std;
int xx;char ff,chh;inline lnt read(){
    xx=ff=0;while(!isdigit(chh)){if(chh=='-'){ff=1;}chh=getchar();}
    while(isdigit(chh)){xx=(xx<<1)+(xx<<3)+chh-'0';chh=getchar();}return ff? -xx: xx;
}
const int N=2e6;
bool solve();
int main(){
	int G=read();
	while(G--){
		if(!solve()){
			puts("Yes");
		}else{
			puts("Baka Chino");
		}
	}
	
	return 0;
}
struct edge{int to,v;};
vector<edge> G[N];
int dis,p,d1[N],d2[N];
void dfs(int u,int fa,int d);
void dfs2(int u,int fa,int d[]){
	for(edge e: G[u]){
		if(e.to==fa){continue;}
		d[e.to]=d[u]+e.v;
		dfs2(e.to,u,d);
	}	
}
bool solve(){
	int n=read(),k=read();
	for(int i=1;i<=n;++i){G[i].clear();}
	for(int i=1;i<n;++i){
		int x=read(),y=read(),v=read();
		G[x].push_back({y,v});
		G[y].push_back({x,v});
	}
	dfs(1,0,0);
	dis=0;
	int l=p;
	dfs(p,0,0);
	//if(dis<k){return 0;}
	d1[l]=0;d2[p]=0;
	dfs2(l,0,d1);
	dfs2(p,0,d2);
	int pd=0;
	for(int i=1;i<=n;++i){
		if(d1[i]>=k && d2[i]>=k){
			pd=1;
			break;
		}
	}
	return pd;
}
void dfs(int u,int fa,int d){
	if(d>=dis){p=u;dis=d;}
	for(edge e: G[u]){
		if(e.to==fa){continue;}
		dfs(e.to,u,d+e.v);
	}
}
/*
1
5 7
1 2 2
1 3 3
1 4 4
1 5 3

*/
2025/1/20 15:57
加载中...