题解：P5984 [PA 2019] Podatki drogowe

· · 题解

本文主要讲随机二分的实现，前面本人觉得是平凡的。目前代码是 loj 最短解。

缝合题，狗屎题。假设我们能二分 x，然后判断 \text{dis}\le x。

然后边分治，确定左半边右半边，然后每个半边类似 CF464E 用线段树维护 n 进制加法和比较。

然后对于每条分治边的两边，双指针一下就行。复杂度 \mathcal{O}(n\log^3 n)。

现在难点在于如何二分。你肯定得二分 \dbinom{n}{2} 条路径做到 \log n 级别。

我们假设能做一个随机二分，具体的，随机取一个排名在 [l,r] 内的路径当 mid，然后做。

类似快排那样，期望显然是对的。

我们把边分治的过程离线下来，有若干个集合 L_i,R_i，表示路径长度可重集是由 \bigcup \limits_i \{d_x+d_y:d_x\in L_i,d_y\in R_i\} 组成。

然后 \sum |L_i|+|R_i|=\mathcal{O}(n\log n)。

然后对于每个 d_x\in L_i，维护 l',r' 表示路径 d_x+d_y 排名在当前 [l,r] 区间内对应的 y 应该在 [l',r'] 范围内。

可能比较抽象，就类似整体二分那样。

然后就确定了排名在 [l,r] 的路径长啥样，我们就在这个范围内随机一个即可。

讲的可能比较抽象，但是应该比现有题解清楚（因为他们甚至都没讲）。

:::info[\mathbf{record}]

// 洛谷 P5984
// https://www.luogu.com.cn/problem/P5984
#include<bits/stdc++.h>
#define P pair<int,int>
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define u64 unsigned long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
mt19937 rnd(time(0));
const int N=5e4+5,C=4e5+5,M=1e7+5,mod=1e9+7;
int n,c;u64 k,v[N];
basic_string<int>f[C],g[C],L[C],R[C],md[C];
namespace T
{
    int tt,ls[M],rs[M],c[M],t,q;u64 s[M];
    void upd(int p,int &x,int y,int l=1,int r=n)
    {
        if(!p) return x=y,void();
        c[x=++tt]=c[y]+1;s[x]=s[y]+v[p];if(l==r) return;
        ls[x]=ls[y],rs[x]=rs[y];int m=(l+r)>>1;
        p<=m?upd(p,ls[x],ls[y],l,m):upd(p,rs[x],rs[y],m+1,r);
    }
    inline bool cmp(int A,int B,int C,int D)
    {
        int l=1,r=n,m;
        while(l!=r)
        {
            m=(l+r)>>1;
            if(s[rs[A]]+s[rs[B]]==s[rs[C]]+s[rs[D]])
                r=m,A=ls[A],B=ls[B],C=ls[C],D=ls[D];
            else
                l=m+1,A=rs[A],B=rs[B],C=rs[C],D=rs[D];
        }
        return c[A]+c[B]<c[C]+c[D];
    }
    void get(int x,int y,int l=1,int r=n)
    {
        if(l==r) return q=1ll*q*n%mod,t=(t+1ll*(c[x]+c[y])*q)%mod,void();
        int m=(l+r)>>1;get(ls[x],ls[y],l,m);get(rs[x],rs[y],m+1,r);
    }
    inline int S(int x,int y){t=0,q=1;get(x,y);return t;}
}
inline bool cmp(int x,int y){return T::cmp(x,0,y,0);}
inline bool CMP(P A,P B){return T::cmp(A.fi,A.se,B.fi,B.se);}//线段树维护 n 进制数
namespace TREE
{
    int m,e,X,Y,I,W,sz[N],rt[N];bool v[N];
    vector<P>G[N];vector<tuple<int,int,int>>E[N];
    inline void ad(int u,int v,int w){G[u].push_back({v,w}),G[v].push_back({u,w});}
    inline void add(int u,int v,int w){E[u].push_back({v,w,++e});E[v].push_back({u,w,e});}
    void TO(int x,int F)
    {
        int z=0;
        for(auto [y,w]:G[x]) if(y^F)
        {
            TO(y,x);
            if(!z) add(x,y,w),z=x;
            else add(z,++m,0),add(z=m,y,w);
        }
    }//三度化
    void gr(int x,int F,int _n)
    {
        sz[x]=1;
        for(auto [y,w,i]:E[x]) if(!v[i]&&y!=F)
        {
            gr(y,x,_n),sz[x]+=sz[y];
            auto D=[&](int x){return max(sz[x],_n-sz[x]);};
            if(D(y)<D(X)) X=x,Y=y,I=i,W=w;
        }
    }
    basic_string<int>g;int SZ;
    void gd(int x,int F)
    {
        SZ++;if(x<=n) g+=rt[x];
        for(auto [y,w,i]:E[x]) if(!v[i]&&y!=F)
            T::upd(w,rt[y],rt[x]),gd(y,x);
    }
    void sol(int x,int _n)
    {
        if(_n==1) return;X=0;gr(x,0,_n);v[I]=1;
        rt[X]=SZ=0;gd(X,Y);int L=SZ;
        sort(g.begin(),g.end(),cmp);swap(f[++c],g);
        T::upd(W,rt[Y],0);SZ=0;gd(Y,X);int R=SZ;
        sort(g.begin(),g.end(),cmp);swap(::g[c],g);//离线下来边分治结果
        int _y=Y;sol(X,L),sol(_y,R);
    }
    inline void init(){m=n;TO(1,0);sol(1,m);}
}
int main()
{
    cin.tie(0)->sync_with_stdio(0);cout.tie(0);cin>>n>>k;
    for(int i=1;i<=n;i++) v[i]=rnd();
    for(int i=1,u,v,w;i<n;i++) cin>>u>>v>>w,TREE::ad(u,v,w);
    TREE::init();u64 al=(u64)n*(n-1)/2;
    for(int i=1;i<=c;i++)
    {
        int s1=sz(f[i]),s2=sz(g[i]);
        L[i].resize(s1);R[i].resize(s1);md[i].resize(s1);
        for(int &j:R[i]) j=s2-1;
    }P m(0,0);int cnt=0,z=-1;
  //终止条件是连续多次取到相同长度的 mid,因为有时候会有多条路径长度相同。
    while(cnt<=5)
    {
        u64 nw=rnd()%al+1,s=0;//随机一条路径
        for(int i=1;nw&&i<=c;i++)
        {
            for(int j=0;j<sz(f[i]);j++)
            {
                int t=R[i][j]-L[i][j]+1;
                if(nw>t) nw-=t;
                else{m={f[i][j],g[i][L[i][j]+nw-1]};nw=0;break;}
            }
        }//L,R 表示实时确定排名在 [l,r] 的路径范围，用于双指针
        for(int i=1;i<=c;i++)
        {
            int k=sz(g[i])-1;
            for(int j=0;j<sz(f[i]);j++)
            {
                k=min(k,R[i][j]);
                while(k>=L[i][j]&&CMP(m,{f[i][j],g[i][k]})) k--;
                s+=k-L[i][j]+1;md[i][j]=k;
            }
        }//双指针查询长度 <= 它的路径条数
        if(s==k) break;
        if(s>k)
        {
            al=s;
            for(int i=1;i<=c;i++) for(int j=0;j<sz(f[i]);j++) R[i][j]=md[i][j];
        }
        else
        {
            k-=s,al-=s;
            for(int i=1;i<=c;i++) for(int j=0;j<sz(f[i]);j++) L[i][j]=md[i][j]+1;
        }//关于 L,R 的 mid 数组即为 md，调整一下范围 
        int t=T::S(m.fi,m.se);cnt+=t==z,z=t;
    }
    return cout<<T::S(m.fi,m.se),0;
}

:::