自动搬运

查看原文

来自洛谷，原作者为

	Zenith_Yeh Don't talk to pigs about learning, because pigs care about feed.

搬运于2025-08-24 22:23:22，当前版本为作者最后更新于2020-08-02 09:52:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看到大家方法都不同。

此处献上换根dp

记一下每个点子树离他最远的三个点的距离 记一下每个点父亲最远距离 然后判断一下>=k就行

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
	char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int maxn=200010;
struct edge{
	int next,to,w;
}a[maxn*2];
int head[maxn],len;
void add(int x,int y,int z){
	a[++len]={head[x],y,z};
	head[x]=len;
}
int i,j,k,n,m,dp[maxn][4];//dp[][0]=每个点父亲最远距离，dp[][1]/[2]/[3]=每个点子树离他最远的三个点的距离。
void dfs(int now,int fa){
	for(int i=head[now];i;i=a[i].next){
		int u=a[i].to;
		if(u==fa)continue;
		dfs(u,now);
		if(dp[u][0]+a[i].w>dp[now][0]){//记录一下
			dp[now][3]=dp[now][2];
			dp[now][2]=dp[now][0];
			dp[now][0]=dp[u][0]+a[i].w;
			dp[now][1]=u;
		}else
		if(dp[u][0]+a[i].w>dp[now][2]){
			dp[now][3]=dp[now][2];
			dp[now][2]=dp[u][0]+a[i].w;
		}else
		if(dp[u][0]+a[i].w>dp[now][3])
			dp[now][3]=dp[u][0]+a[i].w;
	}
}
bool B=true;
void dfs2(int now,int fa,int len){
	for(int i=head[now];i;i=a[i].next){
		int u=a[i].to;
		if(u==fa)continue;
		if(u==dp[now][1])dfs2(u,now,max(len,dp[now][2])+a[i].w);
		else dfs2(u,now,max(len,max(len,dp[now][0])+a[i].w));
	}
	if((len>=k) + (dp[now][0]>=k) + (dp[now][2]>=k)>=2)B=false;//判断
	if(len+dp[now][2]>=k && dp[now][0]+dp[now][2]>=k)B=false;
	if(dp[now][2]+dp[now][3]>=k)B=false;
}
int main(){
	int T;cin>>T;
	while(T--){
		B=true;
		n=read();k=read();
		for(i=1;i<n;i++){
			int x=read(),y=read(),z=read();
			add(x,y,z);add(y,x,z);//加边
		}
		dfs(1,0);dfs2(1,0,0);
		if(B)puts("Yes");
		else puts("Baka Chino");
		for(i=1;i<=n;i++)dp[i][0]=dp[i][1]=dp[i][2]=dp[i][3]=head[i]=0;len=0;//赋初始值
	}
	return 0;
}