luogu 2491 [SDOI2011]消防 / 1099 树网的核 单调队列 + 树上问题

Code: 

#include<bits/stdc++.h>
#define ll long long 
#define maxn 300001  
#define inf 1000000000 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;   
deque<int>Q;  
int n,S,edges,k; 
int hd[maxn],to[maxn<<1],nex[maxn<<1],val[maxn<<1],dis[maxn],fa[maxn],mark[maxn];              
void add(int u,int v,int c)                       
{ 
    nex[++edges]=hd[u],hd[u]=edges,to[edges]=v,val[edges]=c;  
}
void dfs(int u,int ff) 
{ 
    if(dis[u]>dis[k]) k=u;  
    fa[u]=ff;   
    for(int i=hd[u];i;i=nex[i]) 
    {
        int v=to[i]; 
        if(v==ff || mark[v]) continue; 
        dis[v]=dis[u]+val[i],dfs(v,u);            
    }
}
int answer[maxn]; 
map<int,int>pre,back;      
int main()
{ 
    int i,j,x,y; 
    // setIO("input");   
    scanf("%d%d",&n,&S);  
    for(i=1;i<n;++i) 
    {
        int a,b,c; 
        scanf("%d%d%d",&a,&b,&c); 
        add(a,b,c), add(b,a,c); 
    }    
    dis[1]=0, dfs(1,0); 
    x=k, k=0,dis[x]=0,dfs(x,0),y=k;   
    //y->x  
    for(int i=y;i;i=fa[i])  mark[i]=1,pre[i]=dis[i], back[i]=dis[y]-dis[i];    
    int ans=inf,s=y;     
    for(int i=y;i;i=fa[i])      
    {    
        dis[k=0]=0;   
        dis[i]=0, dfs(i,fa[i]),answer[i]=dis[k];            
        while(!Q.empty()&&pre[Q.front()]-pre[i]>S) Q.pop_front();    
        while(!Q.empty()&&answer[i]>=answer[Q.back()]) Q.pop_back();     
        while(pre[s]-pre[i]>S) s=fa[s];           
        Q.push_back(i); 
        int a=answer[Q.front()]; 
        int b=pre[i]; 
        int c=back[s]; 
        ans=min(ans,max(max(a,b),c)); 
    }
    printf("%d
",ans);   
    return 0; 
}