洛谷P7597 「EZEC-8」猜树加强版题解

题意：

这是一道交互题。

有一棵以 $1$ 为根的 $n$ 个点的有根树，您需要通过若干次询问得到这棵树的结构。

您可以使用两种询问：

? 1 u v 通过这种询问，您可以获得 $u$ 和 $v$ 之间的距离。

? 2 u 通过这种询问，您可以获得 $u$ 子树的大小和 $u$ 子树中的所有节点。

请通过使交互库输出不超过 $40000$ 个数，得到这棵树的结构。

交互方式：

输入树的大小 $n$ 以开始交互。

交互过程中，您可以进行题目描述中的两种询问。

对于第一种询问，交互库将会返回一个非负整数，表示 $u$ 节点和 $v$ 节点间的距离。

对于第二种询问，交互库将会先返回一个正整数 $x$，表示 $u$ 子树的大小。接下来会在同一行中返回 $x$ 个正整数，表示 $u$ 子树中的所有节点（节点顺序会被打乱）。

在您确定答案后，请以 ! fa[2] fa[3] … fa[n] 的形式输出一行，停止交互。其中 $fa(i)$ 表示这棵树中 $i$ 号节点的父节点。

在您输出一行后，请清空缓冲区：

在 C++ 中，使用 fflush(stdout) 或 cout.flush()。

在 Pascal 中，使用 flush(output)。

在 Python 中，使用 stdout.flush()。

其它语言请自行查阅文档。

数据范围：

$2 \leq n \leq 5000$，$1\le u,v\le n$。

首先一个简单的想法是，我们询问 $1$ 都每个点的距离，这样可以得到所有点的深度

接着从根节点开始遍历，每次暴力找一个儿子，然后询问它的子树，这样把同一层的点分成各个子树。

显然这么做大约需要 $\mathcal{O}(n^2)$ 次询问，根本过不了。不过好消息是，这只是一个上界。

设节点 $u$ 有 $k$ 个儿子，那只需要算出 $k-1$ 个儿子，就知道剩下那个儿子的子树了。

由于这 $k-1$ 个儿子的询问次数以及他们递归以后的询问次数显著影响总询问数

这使得我们注意到，如何选择剩下的那个儿子，使得这 $k-1$ 个儿子的询问次数较少？

答案是选择重儿子。根据 dsu on tree 的结论，$\sum \operatorname{size}(u)-\operatorname{size}(\operatorname{son} u)$ 的量级在 $\mathcal{O}(n \log n)$ 。

那么问题来了，我们都不知道这棵树是什么样子的，怎么找到重儿子？

由于重儿子是 $u$ 子树里子树最大的那个儿子，

那么在 $u$ 里面任取一个点是在重儿子子树里的概率显然大于其他任何一个儿子。

没错，考虑随机化，在 $u$ 子树里随便选一个节点，然后看看落到哪个儿子子树里了，这个儿子就当重儿子。

显然这个算法会在选错儿子的时候复杂度会退化，于是

在轻儿子越少的时候，复杂度会越慢？
轻儿子越少，意味着重儿子越大，更可能选到重儿子，复杂度会变快？

~~所以越慢就会越快~~。这就是随机化的算法的有趣之处。

时间复杂度 $\mathcal{O}(n^2)$ ，询问次数为 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(5e3 + 15))

mt19937 rd(time(0)); bitset<N> vis;
int n, p, fa[N], son[N], dep[N], sz[N], ch[N][N];
void dfs(int u)
{
    if(!sz[u]) return;
    int tmp = ch[u][rd() % sz[u] + 1];
    shuffle(ch[u] + 1, ch[u] + 1 + sz[u], rd);
    for(int i = 1; i <= sz[u]; i++)
    {
        if(dep[ch[u][i]] == dep[u] + 1)
        {
            if(tmp == ch[u][i]) p = 0;
            else { cout << "? 1 " << ch[u][i] << ' ' << tmp << endl, cin >> p; }
            if(p == dep[tmp] - dep[ch[u][i]]) { son[u] = ch[u][i]; break; }
        }
    }
    vis = 0;
    for(int i = 1, x; i <= sz[u]; i++)
    {
        if(dep[ch[u][i]] == dep[u] + 1 && ch[u][i] != son[u])
        {
            cout << "? 2 " << ch[u][i] << endl; cin >> x; sz[ch[u][i]] = x - 1;
            int cnt = 0;
            for(int j = 1; j <= sz[ch[u][i]] + 1; j++)
            {
                cin >> p; vis[p] = true;
                if(p != ch[u][i]) ch[ch[u][i]][++cnt] = p;
            }
        }
    }
    for(int i = 1; i <= sz[u]; i++)
        if(!vis[ch[u][i]] && ch[u][i] != son[u]) ch[son[u]][++sz[son[u]]] = ch[u][i];
    for(int i = 1; i <= sz[u]; i++)
        if(dep[ch[u][i]] == dep[u] + 1) { fa[ch[u][i]] = u, dfs(ch[u][i]); }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 2; i <= n; i++)
    {
        cout << "? 1 1 " << i << endl;
        cin >> dep[i]; ch[1][++sz[1]] = i;
    }
    dfs(1); cout << "! ";
    for(int i = 2; i <= n; i++) cout << fa[i] << ' ';
    cout << endl;
    return 0;
}