51求调
查看原帖
51求调
540229
hcx2012楼主2025/7/24 10:18
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> g[330];
int d[330];
int mx=0,idx=0;
void dfs(int x,int fa){
    if(d[x]>mx){
        mx=d[x];
        idx=x;
    }
    for(auto [i,j]:g[x]){
        if(i!=fa){
            d[i]=d[x]+j;
            dfs(i,x);
        }
    }
}
int ch[330],chw[330];
int dfs2(int x,int fa){
    int mxx=0;
    int idxx=0;
    int ww=0;
    for(auto [i,j]:g[x]){
        if(i==fa)continue;
        int tsz=dfs2(i,x)+j;
        if(tsz>mxx){
            mxx=tsz;idxx=i;ww=j;
        }
    }
    ch[x]=idxx;
    chw[x]=ww;
    return mxx;
}
int bh[330];
int mxxx;
void dfs3(int l,int r,int x,int fa,int d){
    if(d>mxxx){
        mxxx=d;
    }
    for(auto [i,j]:g[x]){
        if(i==fa)continue;
        if(l<=bh[i]&&bh[i]<=r){
            dfs3(l,r,i,x,0);
        }else{
            dfs3(l,r,i,x,d+j);
        }
    }
}
int gt(int x,int y){
    mxxx=0;
    dfs3(x,y,x,0,0);
    return mxxx;
}
int main(){
    int n,s;
    cin>>n>>s;
    for(int i=1;i<=n-1;i++){
        int u,v,ww;
        cin>>u>>v>>ww;
        g[u].push_back({v,ww});
        g[v].push_back({u,ww});
    }
    dfs(1,0);
    dfs2(idx,0);
    int cnt=0;
    for(int i=idx;i;i=ch[i])bh[i]=++cnt;
    int ans=0x3f3f3f3f;
    for(int i=idx;i;i=ch[i]){
        int d=0;
        for(int j=i;j&&d<=s;j=ch[j]){
            ans=min(ans,gt(i,j));
            d+=chw[j];
        }
    }
    cout<<ans;
    return 0;
}

玄关。

2025/7/24 10:18
加载中...