题解：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. \(p > q\) 且 \(\forall i \isin [1,\min(p, q)]\) 满足 $ F(a_i) = F(b_i)$。
2. \(\exist k \isin [1, \min(p, q)]\) 满足 \(\forall i < k\) 有 \(F(a_i) = F(b_i)\) 且 \(F(a_k) > F(b_k)\)。

条件 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;
}