题解 [PA2019]Podatki drogowe

一粒夸克 · 2022-01-15 11:42:59 · 题解

既然没有题解那我就发一篇吧

这题是三道题的结合体：CF464E The Classic Problem、洛谷 P4178 Tree、S2oj 55. 小芈

可以发现，由于图中只有 n-1 条边，若边权为 n^z ，相加时是不会发生进位的。

因此我们比较两条路径时，只需依次比较每个数字出现的个数即可。

可以用主席树维护哈希值，把单次比较的复杂度优化到 O(\log n)。

考虑二分答案。

我们先进行一次边分治，预处理出所有的“半条路径”，然后排序。

这样一来，对于左边的一条路径，右边和它相加后权值在当前区间内的路径会在一个区间内。

因此，我们可以对于每个左边的路径维护可以和它匹配的右路径的区间，不必维护所有的路径对，并且可以双指针在 O(n\log^2n) （含 O(\log n) 的比较和 O(\log\ n) 的边分治）的时间复杂度内算出一条路径在当前路径集合中的排名。

考虑到边权很大，而路径只有 n^2 条，我们可以去二分路径。

由于我们不好直接找出当前路径集合的中位数，我们可以随机选出一条路径来当作中位数。

因为不同路径的长度有可能相同，我们不能等集合大小为 1 了再停止二分，我们可以人为设定一个二分次数，50~60 最好。

总时间复杂度 O(n\log^3n)

code：

目前同时是洛谷和 LOJ 的 rank1

#include<bits/stdc++.h>
using namespace std;
int n,m,lim;long long k;
vector<int> rt1[400005],rt2[400005];
namespace Main{
    int le[10000005],ri[10000005],siz[10000005],cnt;
    unsigned long long tree[10000005],val[100005];
    int insert(int loc,int y,int l=1,int r=n){
        if(loc<l||loc>r)return y;
        int i=++cnt;tree[i]=tree[y]+val[loc];siz[i]=siz[y]+1;
        if(l!=r){
            int mid=(l+r)>>1;
            le[i]=insert(loc,le[y],l,mid);ri[i]=insert(loc,ri[y],mid+1,r);
        }
        return i;
    }
    inline bool cmp(int a,int b,int c,int d){
        int l=1,r=n;
        while(l!=r){
            int mid=(l+r)>>1;
            if(tree[ri[a]]+tree[ri[b]]!=tree[ri[c]]+tree[ri[d]]){
                l=mid+1;
                a=ri[a];b=ri[b];c=ri[c];d=ri[d];
            }else {
                r=mid;
                a=le[a];b=le[b];c=le[c];d=le[d];
            }
        }
        return siz[a]+siz[b]<siz[c]+siz[d];
    }
    inline bool ccmp(int x,int y){
        return cmp(x,0,y,0);
    }
    vector<int> L[400005],R[400005],pos[400005];
    struct node{
        int x,y;
        node(int _x,int _y){
            x=_x;y=_y;
        }
        inline bool operator <(const node &b)const{
            return cmp(x,y,b.x,b.y);
        }
    };
    long long ans,base=1;
    const long long md=1e9+7;
    void Get(int x,int y,int l=1,int r=n){
        if(l==r){
            base=base*n%md;ans=(ans+(siz[x]+siz[y])*base)%md;
            return ;
        }
        int mid=(l+r)>>1;
        Get(le[x],le[y],l,mid);Get(ri[x],ri[y],mid+1,r);
    }
    inline void main(){
        long long all=0;
        for(int i=1;i<=lim;i++){
            L[i].resize(rt1[i].size());R[i].resize(rt1[i].size());pos[i].resize(rt1[i].size());
            for(auto &it:R[i])it=rt2[i].size()-1;all+=1ll*rt1[i].size()*rt2[i].size();
        }
        node mid(0,0);
        for(int t=1;t<=60;t++){
            long long rk=abs(1ll*rand()*rand()+rand())%all+1;
            for(int i=1;rk&&i<=lim;i++){
                for(int j=0;j<rt1[i].size();j++){
                    int tmp=R[i][j]-L[i][j]+1;
                    if(tmp>=rk){
                        mid=node(rt1[i][j],rt2[i][L[i][j]+rk-1]);
                        rk=0;break;
                    }else rk-=tmp;
                }
            }
            long long tmp=0;
            for(int i=1;i<=lim;i++){
                int r=rt2[i].size()-1;
                for(int j=0;j<rt1[i].size();j++){
                    r=min(r,R[i][j]);
                    while(r>=L[i][j]&&mid<node(rt1[i][j],rt2[i][r]))r--;
                    pos[i][j]=r;tmp+=r-L[i][j]+1;
                }
            }
            if(k==tmp)break;
            else if(k<tmp){
                all=tmp;
                for(int i=1;i<=lim;i++){
                    for(int j=0;j<rt1[i].size();j++)R[i][j]=pos[i][j];
                }
            }else {
                k-=tmp;all-=tmp;
                for(int i=1;i<=lim;i++){
                    for(int j=0;j<rt1[i].size();j++)L[i][j]=pos[i][j]+1;
                }
            }
        }
        Get(mid.x,mid.y);
        printf("%lld",ans);
    }
}
namespace Init{
    int ver[400005],ne[400005],head[200005],cnt=1,val[400005];
    inline void link(int x,int y,int v){
        ver[++cnt]=y;
        ne[cnt]=head[x];
        head[x]=cnt;val[cnt]=v;
    }
    vector<pair<int,int> > son[100005];
    int las[100005];
    void init(int x,int fi){
        for(auto it:son[x]){
            int u=it.first;if(u==fi)continue;
            init(u,x);
            if(!las[x])link(x,u,it.second),link(u,x,it.second),las[x]=x;
            else {
                link(las[x],++m,0);link(m,las[x],0);las[x]=m;
                link(las[x],u,it.second);link(u,las[x],it.second);
            }
        }
    }
    int siz[200005],mxp[200005],root;
    bool vis[400005];
    void findrt(int x,int fi,int tot){
        siz[x]=1;
        for(int i=head[x];i;i=ne[i]){
            int u=ver[i];if(vis[i]||u==fi)continue;
            findrt(u,x,tot);siz[x]+=siz[u];mxp[i>>1]=max(tot-siz[u],siz[u]);
            if(mxp[root]>mxp[i>>1])root=(i>>1);
        }
    }
    int rt[200005];
    vector<int> vec;
    void dfs(int x,int fi){
        if(x<=n)vec.push_back(rt[x]);
        siz[x]=1;
        for(int i=head[x];i;i=ne[i]){
            int u=ver[i];
            if(vis[i]||u==fi)continue;
            rt[u]=Main::insert(val[i],rt[x]);
            dfs(u,x);siz[x]+=siz[u];
        }
    }
    void solve(int x,int tot){
        mxp[root=0]=m;findrt(x,x,tot);
        if(!root)return ;vis[root<<1]=vis[root<<1|1]=1;
        int L=ver[root<<1],R=ver[root<<1|1];++lim;
        rt[L]=0;vec.clear();dfs(L,R);
        sort(vec.begin(),vec.end(),Main::ccmp);swap(rt1[lim],vec);
        rt[R]=Main::insert(val[root<<1],0);vec.clear();dfs(R,L);
        sort(vec.begin(),vec.end(),Main::ccmp);swap(rt2[lim],vec);
        solve(L,siz[L]);solve(R,siz[R]);
    }
    inline void main(){
        for(int i=1;i<=n;i++)Main::val[i]=1ll*rand()*rand()*rand()+1ll*rand()*rand()+rand();
        for(int i=1;i<n;i++){
            int x,y,v;
            scanf("%d%d%d",&x,&y,&v);
            son[x].push_back(make_pair(y,v));
            son[y].push_back(make_pair(x,v));
        }m=n;
        init(1,1);solve(1,m);
    }
}
int main(){
    scanf("%d%lld",&n,&k);
    Init::main();
    Main::main();

    return 0;
}