题解：CF2135F To the Infinity

· · 题解

更好的阅读体验

学生零太强大了。

下文中 F(u) = f_u(x)。首先我们考虑单个点 u 的 F 如何计算，如图。

由定义，F(u) = F(a_1) ^{F(b_1)} = F(a_2)^{F(b_1) F(b_2)} = \cdots = F(p)^{F(b_1) F(b_2) F(b_3) F(b_4)}。

又因为 p 是叶子，所以 F(p) = x。考虑求出 F(u) 以 x 为底的对数，则可以得到 \log_x F(u) 是若干个 F(v) 的乘积。

接下来考虑如何比较两个 F(u) 和 F(v) 的大小。

我们假设 \log_x F(u) = \prod \limits_{i = 1}^{p} F(a_i), \log_x F(v) = \prod \limits_{i = 1}^{q} F(b_i)。比较 F(u) 和 F(v) 的大小等价于比较 \prod \limits_{i = 1}^{p} F(a_i) 和 \prod \limits_{i = 1}^{q} F(b_i) 的大小。

我们声称，F(u) > F(v) 等价于，我们分别将 F(a_i) 和 F(b_i) 从大到小排序后，F(a_i) 序列的字典序比 F(b_i) 的字典序大。更正式地，以下条件至少满足一个：

条件 1 的正确性显然。

证明条件 2 等价于证明 \prod\limits_{i = k}^q F(b_i) < F(a_k)。

由于 F 是 Power tower，因此若 F(u) > F(v)，则有 F(u) \ge F^x(v)。

由此放缩 \prod\limits_{i = k}^q F(b_i) \le F^n(b_k)。由于 x \to +\infty，因此 F^n(b_k) < F^x(b_k) < F(a_k)，得证。

这样问题就简单了许多。

我们仍然无法直接比较两个 F 的大小，但是我们可以维护其相对的排名 rk，rk_u 表示 F(v) < F(u) 的 v 的个数 +1。由定义我们就能发现，对于 F(u) 相同的 u，rk_u 也是相等的。

同时有一个很好的性质：一个点的 rk 一定比它的儿子的 rk 要大。所以我们可以拓扑排序。

具体地，我们维护一个小根堆，每次取出堆顶 u。由于这个堆顶是堆中最小元素，因此 rk 比当前 rk_u 小的所有点都已经被计算过了，因此这个时候对 u 求出的排名就是最终的 rk。

我们用主席树维护哈希值，可以方便地二分一个后缀比较两个序列字典序的大小。我们对每个点存下 \log_x F(u) 是由哪几个 F(v) 的乘积构成的，然后将 v 挂在主席树上 rk_v 的下标处。

我们取出 u 之后，假设 u 的父亲是 f。如果 f 的两个儿子都已经出堆过了，那么我们将 f 插入堆中，这时 f 对应的主席树应继承 f 左儿子的主席树，同时再将 u 的右儿子 r 挂在主席树 rk_r 对应的下标下。

重复这个过程就可以求出每个点的 rk，继而求出排序后的序列。

注意到堆的每一次比较都需要调用一次主席树上二分，因此单组数据复杂度为 O(n \log^2 n)。

#include<bits/stdc++.h>
#define endl '\n'
#define N 400006
using namespace std;
using u64=unsigned long long;
int n,tp,deg[N],rt[N],l[N],r[N],fa[N],rk[N],ans[N];
u64 pw[N];
struct HJT {
    int tot,ls[N<<5],rs[N<<5];
    struct Node {
        u64 hs; int sz;
        Node(u64 hs=0,int sz=0):hs(hs),sz(sz) {}
        friend Node operator +(Node x,Node y)
        {
            Node ret;
            ret.sz=x.sz+y.sz,ret.hs=x.hs*pw[y.sz]+y.hs;
            return ret;
        }
    } tree[N<<5];
    void clear()
    {
        for(int i=1;i<=tot;i++)ls[i]=rs[i]=0,tree[i]=Node();
        tot=0;
    }
    void update(int &p,int q,int l,int r,int k)
    {
        p=++tot;
        tree[p]=tree[q],ls[p]=ls[q],rs[p]=rs[q];
        if(l==r)return tree[p]=tree[p]+Node(l,1),(void)0;
        int mid=l+r>>1;
        k<=mid?update(ls[p],ls[q],l,mid,k):
               update(rs[p],rs[q],mid+1,r,k);
        tree[p]=tree[ls[p]]+tree[rs[p]];
    }
    int cmp(int p,int q,int l,int r,int rp,int rq)
    {
        if(tree[p].hs==tree[q].hs)return rp>rq;
        if(!p||!q||l==r)return tree[p].sz>tree[q].sz;
        int mid=l+r>>1;
        u64 hs_rp=tree[rs[p]].hs,hs_rq=tree[rs[q]].hs;
        if(hs_rp==hs_rq)return cmp(ls[p],ls[q],l,mid,rp,rq);
        return cmp(rs[p],rs[q],mid+1,r,rp,rq);
    }
} T;
struct Data {
    int u;
    Data(int u):u(u) {}
    friend bool operator >(Data x,Data y) {return T.cmp(rt[x.u],rt[y.u],1,n,x.u,y.u);}
};
inline int eq(int u,int v) {return T.tree[rt[u]].hs==T.tree[rt[v]].hs;}
priority_queue<Data,vector<Data>,greater<Data> > q;
void solve()
{
    scanf("%d",&n),T.clear(),tp=0;
    while(q.size())q.pop();
    for(int i=1;i<=n;i++)deg[i]=rt[i]=l[i]=r[i]=fa[i]=rk[i]=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&l[i],&r[i]);
        if(l[i])fa[l[i]]=fa[r[i]]=i,deg[i]=2;
        else T.update(rt[i],0,1,n,rk[i]=1),q.push(i),deg[i]=0;
    }
    while(q.size())
    {
        int u=q.top().u; q.pop();
        rk[u]=rk[ans[tp]]+!eq(ans[tp],u),ans[++tp]=u;
        if(!--deg[fa[u]])
            T.update(rt[fa[u]],rt[l[fa[u]]],1,n,rk[r[fa[u]]]),q.push(fa[u]);
    }
    for(int i=1;i<=n;i++)
        printf("%d%c",ans[i]," \n"[i==n]);
}
main()
{
    int T; scanf("%d",&T),pw[0]=1;
    for(int i=1;i<N;i++)pw[i]=pw[i-1]*1145141;
    while(T--)solve();
    return 0;
}