题解 P6722 【「MCOI-01」Village 村庄】

Zenith_Yeh · 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;
}