题解：P11946 [KTSC 2025] 信竞天择 2 / evolution
沉石鱼惊旋
·
·
题解
题意
一棵 n 个节点的有根树，以 0 为根。每个点 u 有一个 p_u。对于所有 u，u 的父亲 fa 总是满足 p_{fa}\lt p_u。
你可以给出 u\neq v 的一对 u,v 调用交互库 \operatorname{compare}(u,v) 查询 [p_u\lt p_v] 。
还原排列。
设 P 表示这棵树所有可能的 p 的个数，Z=\lceil \log_2 P\rceil，你调用了 C 次交互库，令 K=C/Z。当 Z=0 的时候，如果 C\gt 0，那么 K=10^9，否则 K=0。只有 K\leq 1.4 时才能获得满分。
# 做法
设 $V_u$ 表示 $u$ 子树内排好序的序列。
初始 $V_u$ 为空，之后一直加入 $V_v(v\in \operatorname{son}(u))$。把 $V_u$ 和 $V_v$ 合并起来。全部合并完之后把 $u$ 插到 $V_u$ 开头。
考虑优化这个插入的部分。
一个想法是分块，设合并的序列是 $V_1,V_2$，长度 $L_1,L_2$ 且 $L_1\geq L_2$。块长设为 $B$。然后取出 $V_1$ 每个块第一个元素和 $V_2$ 归并排序。最后在块内二分出这个元素最后的位置。
这个做法需要 $\lceil L_1/B \rceil+L_2-1+L_2\times (\lceil\log_2(B-1)\rceil+1)$ 次操作。
考虑尽量把这个 $B$ 卡到 $2^k+1$。这样块内二分次数不变。但是归并次数可以变少。
直接这样做分够高了但是过不去。大概有八十多分。
如果 $V_2$ 元素很少 $V_1$ 元素很多我们还有 $L_2\times \lceil\log_2(L_1+1)\rceil$ 次操作的做法。就是直接把整个序列看成一块直接二分（不用取出第一个元素）。
分块策略枚举块长算一个最优解出来，和第二种做法次数比较一下，选择次数更小的策略。这里次数写出来的式子要卡精细一点。
# 代码
<https://qoj.ac/submission/951035>
```cpp
#include <bits/stdc++.h>
#include "evolution2.h"
using namespace std;
vector<int> recover(int N, vector<int> U, vector<int> V)
{
int n = N;
vector<int> p;
vector<vector<int>> a(n);
vector<vector<int>> vec(n);
for (int i = 0; i < n - 1; i++)
{
auto [u, v] = tie(U[i], V[i]);
a[u].emplace_back(v);
a[v].emplace_back(u);
}
auto merge = [&](vector<int> &a, vector<int> &b)
{
if (a.empty())
return b;
if (b.empty())
return a;
if (a.size() < b.size())
swap(a, b);
vector<int> t;
int cnt = a.size() + b.size() - 1, l = 0;
auto upd = [&](int len)
{
int times = (a.size() + len) / (len + 1) + b.size() - 1 + b.size() * (__builtin_ctz(len) + 1);
if (times < cnt)
cnt = times, l = len;
};
int len = 1;
upd(len);
while (len + 1 < a.size())
{
len <<= 1;
upd(len);
}
len = l + 1;
l = 1;
while (l < a.size() + 1)
l <<= 1;
vector<int> v;
int i = 0, j = 0;
vector<int> pos(b.size());
if (b.size() * __builtin_ctz(l) < cnt)
{
for (int p = 0; p < b.size(); p++)
{
pos[p] = !p ? -1 : pos[p - 1];
int l = !p ? 0 : pos[p - 1] + 1, r = a.size() - 1;
while (l <= r)
{
int mid = l + r >> 1;
if (compare(a[mid], b[p]))
l = (pos[p] = mid) + 1;
else
r = mid - 1;
}
if (pos[p] == -1)
v.emplace_back(b[p]);
}
}
else
{
for (int i = 0; i < a.size(); i += len)
t.emplace_back(a[i]);
int c = 0;
while (i < t.size() || j < b.size())
{
if (i == t.size())
v.emplace_back(-(++j));
else if (j == b.size())
v.emplace_back((i++) * len);
else if (compare(t[i], b[j]))
v.emplace_back((i++) * len);
else
v.emplace_back(-(++j));
}
int lst = -1;
t = v;
v.clear();
for (int p : t)
{
if (p >= 0)
lst = p;
else
{
p = -p - 1;
if (~lst)
{
pos[p] = lst;
int l = lst + 1, r = min((int)a.size() - 1, lst + len - 1);
while (l <= r)
{
int mid = l + r >> 1;
c++;
if (compare(a[mid], b[p]))
l = (pos[p] = mid) + 1;
else
r = mid - 1;
}
}
else
{
pos[p] = -1;
v.emplace_back(b[p]);
}
}
}
}
i = 0, j = 0;
while (pos[j] == -1)
j++;
while (i < a.size() || j < b.size())
{
if (i == a.size())
v.emplace_back(b[j++]);
else if (j == b.size())
v.emplace_back(a[i++]);
else if (i <= pos[j])
v.emplace_back(a[i++]);
else
v.emplace_back(b[j++]);
}
return v;
};
auto dfs = [&](auto self, int u, int fa) -> void
{
for (int v : a[u])
{
if (v == fa)
continue;
self(self, v, u);
vec[u] = merge(vec[u], vec[v]);
}
vec[u].insert(vec[u].begin(), u);
};
dfs(dfs, 0, -1);
p = vec[0];
vector<int> q(n);
for (int i = 0; i < n; i++)
q[p[i]] = i;
return q;
}
```