bzoj 1999: [Noip2007]Core树网的核

.

题意：给出一棵树，在它的直径上找到一条长度不超过s的路径，使其他点到这条路径的最大距离最小
题解：树的直径+单调队列
可以证明，在任意一条直径上都能找到答案，所以之间求出一条，搞个单调队列就好了。
代码：

#include<bits/stdc++.h>
using namespace std;

int n,s,fst[500010],num=0,dis[500010],pre[500010],sum[500010],ans=2147483647/*,tim=0*/;
bool v[500010];
struct edge
{
    int x,y,c,n;
}e[1000010];
vector<int>d;

void ins(int x,int y,int c)
{
    e[++num]={x,y,c,fst[x]};
    fst[x]=num;
}
int bfs(int s)
{
    // puts("");
    static queue<int>q;
    q.push(s);
    v[s]=1;
    pre[s]=0;
    dis[s]=0;
    int ans=s;
    while(!q.empty())
    {
        int x=q.front();/*
        tim++;
        printf("%d\n",x);*/
        q.pop();
        if(dis[x]>dis[ans])
        ans=x;
        for(int i=fst[x];i;i=e[i].n)
        {
            int y=e[i].y;
            if(!v[y])
            {
                pre[y]=x;
                dis[y]=dis[x]+e[i].c;
                v[y]=1;
                q.push(y);
            }
        }
    }
    return ans;
}
void getd()
{
    memset(v,0,sizeof(v));
    int a=bfs(1);
    memset(v,0,sizeof(v));
    int b=bfs(a);
    for(int i=b;i;i=pre[i])
    {
        sum[d.size()]=dis[b]-dis[i];
        d.push_back(i);
    }
}
int main()
{
    scanf("%d%d",&n,&s);
    for(int i=1;i<n;i++)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        ins(x,y,c);
        ins(y,x,c);
    }
    getd();
    int sz=d.size();
    memset(v,0,sizeof(v));
    for(int i=0;i<sz;i++)
    {
        v[d[i]]=1;
    }
    deque<pair<int,int> >q;
    for(int i=0,l=0;i<sz;i++)
    {
        // tim=0;
        int hh=dis[bfs(d[i])];
        // printf("%d %d\n",d[i],sum[i]);
        while(!q.empty()&&q.back().first<hh)
        q.pop_back();
        q.push_back(make_pair(hh,i));
        while(sum[i]-sum[q.front().second]>s)
        q.pop_front();
        while(sum[i]-sum[l]>s)
        l++;
        int oo=max(max(q.front().first,sum[l]),sum[sz-1]-sum[i]);
        ans=min(ans,oo);
    }
    printf("%d",ans);
}