题解 P4292 【[WC2010]重建计划】

· · 题解

这里是某可能假掉的n\log n算法。证明不太严谨，如果你把它叉掉了或者可以提供更美妙的证明欢迎私信或者发帖联系。

照着[BJOI2017]树的难题的思路，我们可以很自然地想到这题仍然可以使用单调队列按秩合并，即将分治树中所有点按照深度递增排序，则可选深度区间一定是递减的。因为这一区间是递减的，所以就可以使用单调队列维护。更详细的解释可以在本人的点分治学习笔记找到或者参阅其它神仙的题解。

这里主要是探讨n\log n的做法，即不在外面套上\log n的二分的算法。

我们设当前探讨的点是x，它的深度是dep_x，到根的路径权值为sum_x。再设所有其它路径中，深度为k的路径最大的权值为buc_k。单调队列中存储的是深度，按照从队首到队尾递减。

因为x已经按照深度排序了，所以必有dep_x\nearrow。其它值都没有任何性质。

我们考虑这样一种贪心策略：

当从队尾加入新元素时，只要当前队尾的那条路径与x拼合起来的结果小于新元素与x拼合的结果，就弹出队尾。

设队尾元素为a，新元素为b，必有a>b。则只要\dfrac{buc_a+sum_x}{a+dep_x}\leq\dfrac{buc_b+sum_x}{b+dep_x}成立，a就应该被弹出。

现在我们要来证明，被弹出的a再往后都不会成为解。

显然，当dep_x\nearrow时，两边的值都是下降的。故因为此时有\dfrac{buc_a+sum_x}{a+dep_x}\leq\dfrac{buc_b+sum_x}{b+dep_x}，再往后的值一定更劣，故不如此时就选择b。

但是我们没有考虑到，万一sum_x也跟着\nearrow怎么办？

则显然，此时a增加的更少。

如果sum_x增加的速度小于对应的dep_x增加的速度，则答案肯定会变得更劣，故就算a可能到那时会更优，那更优的答案也会小于此时b的答案；如果sum_x增加速度大于dep_x增加的速度，则就是b更优了。故a无论如何都可以弹出。

那么队首呢？设其为c。

首先，只要队首已经不合法了（即c+dep_x>R），就必须被弹掉，这点毫无疑问。

然后，我们考虑队首的下一位为d。则只要\dfrac{buc_c+sum_x}{c+dep_x}\leq\dfrac{buc_d+sum_x}{d+dep_x}，c就应该被弹掉。

这个格式同队尾的基本一致，故也可以类似地证明。

则我们只要采取bfs解法，就可以在O(n\log n)时间内解出本题。

当然这个证明不很严谨，欢迎来叉。

代码：

#pragma GCC optimize(3)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
const ll fni=-1e11;
int n,L,R;
double mx;
int ROOT,SZ,sz[200100],msz[200100];
int dep[200100],mdp[200100],lim;
ll sum[200100],buc[200100];
vector<pair<int,int> >v[200100];
bool vis[200100];
void getsz(int x,int fa){
    sz[x]=1;
    for(auto i:v[x])if(!vis[i.first]&&i.first!=fa)getsz(i.first,x),sz[x]+=sz[i.first];
}
void getroot(int x,int fa){
    sz[x]=1,msz[x]=0;
    for(auto i:v[x])if(!vis[i.first]&&i.first!=fa)getroot(i.first,x),sz[x]+=sz[i.first],msz[x]=max(msz[x],sz[i.first]);
    msz[x]=max(msz[x],SZ-sz[x]);
    if(msz[x]<msz[ROOT])ROOT=x;
}
void getdep(int x,int fa,int fr){
    mdp[fr]=max(mdp[fr],dep[x]);
    for(auto i:v[x])if(!vis[i.first]&&i.first!=fa)dep[i.first]=dep[x]+1,sum[i.first]=sum[x]+i.second,getdep(i.first,x,fr);
}
bool cmp(pair<int,int>x,pair<int,int>y){
    return mdp[x.first]<mdp[y.first];
}
queue<int>q;
deque<int>dq;
void bfsread(int x){
    dq.clear();
    q.push(x);
    int tmp=lim;
    while(!q.empty()){
        x=q.front(),q.pop();
        while(tmp>=0&&tmp+dep[x]>=L){
            while(!dq.empty()&&(buc[tmp]+sum[x])*(dq.back()+dep[x])>=(buc[dq.back()]+sum[x])*(tmp+dep[x]))dq.pop_back();
            dq.push_back(tmp--);
        }
        while(!dq.empty()&&dq.front()+dep[x]>R)dq.pop_front();
        while(dq.size()>=2&&(buc[dq[0]]+sum[x])*(dq[1]+dep[x])<=(buc[dq[1]]+sum[x])*(dq[0]+dep[x]))dq.pop_front();
        if(!dq.empty())mx=max(mx,1.0*(buc[dq.front()]+sum[x])/(dq.front()+dep[x]));
        for(auto i:v[x])if(!vis[i.first]&&dep[i.first]>dep[x])q.push(i.first);
    }
}
void bfswrite(int x){
    q.push(x);
    while(!q.empty()){
        x=q.front(),q.pop();
        buc[dep[x]]=max(buc[dep[x]],sum[x]),lim=max(lim,dep[x]);
        for(auto i:v[x])if(!vis[i.first]&&dep[i.first]>dep[x])q.push(i.first);
    }
}
void calc(int x){
    sum[x]=dep[x]=0;
    for(auto i:v[x])if(!vis[i.first])sum[i.first]=i.second,dep[i.first]=1,getdep(i.first,x,i.first);
    sort(v[x].begin(),v[x].end(),cmp);
    for(auto i:v[x])if(!vis[i.first])mdp[i.first]=0,bfsread(i.first),bfswrite(i.first);
    for(int i=1;i<=lim;i++)buc[i]=fni;lim=0;
}
void solve(int x){
    calc(x);
    getsz(x,0); 
    vis[x]=true;
    for(auto i:v[x])if(!vis[i.first])ROOT=0,SZ=sz[i.first],getroot(i.first,0),solve(ROOT);
}
void read(int &x){
    x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
int main(){
    read(n),read(L),read(R);
    for(int i=1;i<=n;i++)buc[i]=fni;
    for(int i=1,x,y,z;i<n;i++)read(x),read(y),read(z),v[x].push_back(make_pair(y,z)),v[y].push_back(make_pair(x,z));
    msz[0]=n+1,SZ=n,getroot(1,0),solve(ROOT);
    printf("%.3lf\n",mx);
    return 0;
}