Solution

Vol 2

SDOI2011 消防

BZOJ2282

题目是给出了一棵树，要求树上的一段路径，让这段路径的长度小于等于某个定值S，并使所有不在路径上的点到路径的距离的最大值最小。

直觉上，我们可以二分这个距离，然后对于每个点维护与它距离不超过这么多的点集，这显然是一棵树，最后将所有点的树求交。

这可以用LCT完成……虽然考虑到代码量，这算法想想就好。

直觉告诉我，不是省选压轴题的本题，标算不可能这么SXBK……

这道题要优化的目标，很直观地会让我们猜测它必然和直径有关系。

一个命题：对任意直径，必然存在一个最优化方案，使该路径落在直径上。

首先，如果一个最优化方案与直径交集为空，考虑把它“扯”到直径上，减去覆盖部分后我们会发现，直径的一部分不如最优方案的一部分长，这与直径的定义矛盾。用类似的方法，可以证明它必然落在直径上。

然后用一个简单的单调队列就可以了。

这道题网络上流传的解法主要是在直径上二分……这是可以卡的。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Edge{
    int from,to,w;
    Edge(){
        from=to=0;
        w=0;
    } 
    Edge(int from_,int to_,int w_){
        from=from_,to=to_;
        w=w_; 
    }
};
const int maxn=300005,INF=0x3f3f3f3f;
vector<Edge> G[maxn];
int next[maxn];
int NextW[maxn];
int DiameterFrom;
int OnDiameter[maxn];
deque<int> Q;
int pre[maxn];
int MaxDis[maxn];
int cnt;
int n,S;
namespace GetDiameter{
    int dis[maxn];
    int GetFar(int u,int f)
    {
        int ans=u;
        for(int i=0;i<G[u].size();i++){
            Edge e=G[u][i];
            if(e.to==f)
                continue;
            int tot=GetFar(e.to,u);
            if(dis[e.to]+e.w>dis[u])
                ans=tot,dis[u]=dis[e.to]+e.w;
        }
        return ans;
    }
    void DfsDiameter(int u,int f)
    {
        next[u]=-1;
        for(int i=0;i<G[u].size();i++){
            Edge e=G[u][i];
            if(e.to==f)
                continue;
            DfsDiameter(e.to,u);
            if(dis[e.to]+e.w>dis[u])
                dis[u]=dis[e.to]+e.w,next[u]=e.to,NextW[u]=e.w;
        }
    }
    void Solve()
    {
        memset(dis,0,sizeof(dis));
        DiameterFrom=GetFar(1,-1);
        memset(dis,0,sizeof(dis));
        DfsDiameter(DiameterFrom,-1);
        memset(OnDiameter,false,sizeof(OnDiameter));
        int u=DiameterFrom;
        while(u!=-1){
            OnDiameter[u]=true;
            u=next[u];
        }
    }
}
void Dfs(int u,int f)
{
    for(int i=0;i<G[u].size();i++){
        Edge e=G[u][i];
        if(e.to==f||OnDiameter[e.to])
            continue;
        Dfs(e.to,u);
        MaxDis[u]=max(MaxDis[u],MaxDis[e.to]+e.w); 
    }
}
void First()
{
    GetDiameter::Solve();
    int u=DiameterFrom;
    while(u!=-1){
        Dfs(u,-1);
        if(next[u]!=-1)
            pre[next[u]]=pre[u]+NextW[u];
        cnt=u;
        u=next[u];
    }
}
void Solve()
{
    int ans=INF;
    int l=DiameterFrom,r=l;Q.push_back(l);
    int p=-1; 
    while(l!=-1){
        if(Q.front()==p)
            Q.pop_front();
        while(next[r]!=-1&&pre[next[r]]-pre[l]<=S){
            while(!Q.empty()&&MaxDis[Q.back()]<MaxDis[next[r]])
                Q.pop_back();
            Q.push_back(next[r]);
            r=next[r];
        }
        ans=min(ans,max(max(pre[l],pre[cnt]-pre[r]),MaxDis[Q.front()]));
        p=l;
        l=next[l];
    }
    cout<<ans<<endl;
}
void AddEdge(int u,int v,int w)
{
    G[u].push_back(Edge(u,v,w));
    G[v].push_back(Edge(v,u,w));
}
void ReadData()
{
    scanf("%d%d",&n,&S);
    for(int i=1;i<n;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        AddEdge(u,v,w);
    }
}
void Freopen()
{
    freopen("loli.in","r",stdin);
}
void Close()
{
    fclose(stdin);
    fclose(stdout); 
} 
int main()
{
    Freopen();
    ReadData();
    First();
    Solve();
    Close();
    return 0;   
}