1 条题解

  • 2
    //双指针尺取法O(n)秒杀
    #include<bits/stdc++.h>
    using  namespace std;
    typedef long long ll;
    const ll N=1000001;
    ll n,m=0,i,j,ans=LONG_LONG_MAX,x,y,z,ma,rt1,rt2,s;
    ll e[N],w[N],ne[N],head[N],tot=0;
    ll dis[500001],pre[500001]={0},f[500001],a[500001];
    bool vis[500001];
    void add(ll u,ll v,ll w1)
    {
        tot++;
        e[tot]=v;w[tot]=w1;ne[tot]=head[u];head[u]=tot;
    }
    void dfs(ll x)
    {
        vis[x]=1;
        for(ll i=head[x];i!=-1;i=ne[i])
        {
            ll j=e[i];
            if(vis[j]==0)
            {
                dfs(j);
                f[x]=max(f[x],f[j]+w[i]);
            }
        }
    }
    void bfs(ll x)
    {
        queue<ll> q;
        q.push(x);
        while(!q.empty())
        {
            ll u=q.front();
            q.pop();//cout<<u<<" "<<q.size()<<endl;
            for(ll i=head[u];i!=-1;i=ne[i])
            {
                ll j=e[i];//cout<<i<<" ";
                if(dis[j]>dis[u]+w[i]&&vis[j]==0)
                {
                    dis[j]=dis[u]+w[i];vis[j]=1;
                    pre[j]=u;q.push(j);
                }
            }
        }
    //  cout<<"b";
    }
    int main()
    {
    //  std::ios::sync_with_stdio(false);万恶之源爆bfs
        memset(head,-1,sizeof head);
        cin>>n>>s;
        for(i=1;i<n;i++)
        {
            cin>>x>>y>>z;
            add(x,y,z);add(y,x,z);
        }
        memset(dis,0x3f,sizeof dis);dis[1]=0;
        memset(vis,0,sizeof vis);vis[1]=1;
        bfs(1);ma=LONG_LONG_MIN;
        for(i=1;i<=n;i++)
            if(dis[i]>ma)
            {
                ma=dis[i];rt1=i;
            }
    //  cout<<"a";
        memset(dis,0x3f,sizeof dis);dis[rt1]=0;
        memset(vis,0,sizeof vis);vis[rt1]=1;
        bfs(rt1);ma=LONG_LONG_MIN;//cout<<"c";
        for(i=1;i<=n;i++)
            if(dis[i]>ma)
            {
                ma=dis[i];rt2=i;
            }
        //cout<<"a";
        memset(vis,0,sizeof vis);x=rt2;
        while(x!=rt1)
        {
            vis[x]=1;a[++m]=x;
            x=pre[x];
        }
        a[++m]=rt1;vis[rt1]=1;
        for(i=1;i<=m;i++)dfs(a[i]);//cout<<a[i]<<" "<<v[a[i]]<<endl;//cout<<endl;
        ma=LONG_LONG_MIN;
        for(i=1;i<=m;i++)ma=max(ma,f[a[i]]);//cout<<f[a[i]]<<endl;
        j=m;//cout<<"b";
        for(i=m;i>=1;i--)
        {
            while(j>=1&&dis[a[j]]-dis[a[i]]<=s)j--;
            //cout<<ans<<" "<<max(dis[a[i]],dis[a[1]]-dis[a[j+1]])<<endl;
            ans=min(ans,max(dis[a[i]],dis[a[1]]-dis[a[j+1]]));
        }
        cout<<max(ans,ma);
        return 0;
    }
    /*
    5 46
    1 2 5
    1 3 15
    1 5 6
    2 4 28
    */
    
    
  • 1

信息

ID
1382
难度
9
分类
树结构 点击显示
标签
递交数
3
已通过
3
通过率
100%
上传者