1 条题解
-
212107张凌睿 (202112107张凌睿) LV 10 @ 2024-07-29 11:09:59
//双指针尺取法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