LOJ6669 Nauuo and Binary Tree 题解

题意：

Nauuo 是一个喜欢二叉树的女孩子（~~cxy 就不一样，她喜欢妹纸~~）。

这天，她创造了一个有 \(n\) 个节点的二叉树。节点的编号从 \(1\) 到 \(n\) ，其中 \(1\) 是二叉树的根节点。

不过，她不记得这棵二叉树具体长什么样子了，她只记录了二叉树上任意两个节点之间的距离。你可以通过向她询问有关距离的信息来还原这棵二叉树，两个节点之间的距离定义为它们之间最短路上的边数。

你可以向 Nauuo 询问不超过 \(30000\) 次有关距离的信息。你只需要告诉她 \(2\sim n\) 号节点的父亲的编号就可以了。

交互方式

最开始，交互器会向标准输入中输入一个正整数 \(n\)。

接下来，你可以通过标准输出向交互器询问两个节点之间的距离。

对于一次询问，你需要输出一行 ? u v 表示你想让 Nauuo 告诉你节点 \(u\) 和节点 \(v\) 在这棵二叉树上距离，然后换行并刷新缓存。

在每次询问后，交互器会向标准输入中输入一个非负整数 \(d\)，表示节点 \(u\) 和节点 \(v\) 之间的距离。

当你的所有询问结束后，你需要输出一行 ! p，\(p\) 是一个长为 \(n-1\) 的正整数序列，第 \(i\) 个数表示第 \(i+1\) 个节点在这棵二叉树上的父亲，然后换行并刷新缓存。

当你的程序正确时，保证交互器使用的时间不会超过 \(500\ \text{ms}\)。

如果你的询问次数超过 \(30000\) 次，那么评测机将会返回 Wrong Answer 或 Time Limit Exceeded，你的程序将会获得 \(0\) 分。

如果你的程序没有及时刷新缓存，那么评测机将会返回 Time Limit Exceeded，你的程序将会获得 0 分。

如果你的程序使用 C++，可以使用 fflush(stdout) 或 cout.flush() 或 cout << endl 来刷新缓存；

如果你的程序使用 Java，可以使用 System.out.flush() 来刷新缓存；

如果你的程序使用 Pascal，可以使用 flush(output) 来刷新缓存；

如果你的程序使用 Python，可以使用 stdout.flush() 来刷新缓存。

对于全部的数据，\(2\le n\le 3000\)。

你输出的 \(u,v\) 应该满足 \(1\le u,v\le n\)，\(p_i\) 应该满足 \(1\le p_i\le n\)，否则评测机会返回 Wrong Answer。

保证交互器输出的 \(d\) 满足 \(0\le d\le n-1\)。

考虑先询问每个到 \(1\) 的距离，得到所有节点的深度，然后依次考虑每一层。

假设目前已经处理完了前 \(d - 1\) 层，考虑第 \(d\) 层的一个点 \(v\) 如何接上当前的树。

容易发现，任意一点 \(u\) 均有 \(\operatorname{dep} {\small\mathrm{L C A}(u, v)}=\frac{\operatorname{dep} u+\operatorname{dep} v-\operatorname{dist}(u, v)}{2}\) ，于是可以得到他们 LCA 的深度。

于是我们取 \(u\) 为当前 \(d-1\) 树的一个叶节点，并设 \(1\) 到 \(u\) 的链为 \(\langle 1,u_1,u_2\cdots,u_k=u\rangle\) ，记 \(u_l=\mathrm{L C A}(u, v)\)

然后我们得到 \(\operatorname{dist}\left(u_l, v\right)\) 的值，如果为 \(1\) 则找到了 \(v\) 的父节点，否则将 \(u_l\) 的另一个儿子当作根重复操作。

这里的“另一个”指的是非 \(u_{l+1}\) 那个儿子，或者说不在 \(\langle 1,u_1,u_2\cdots,u_k=u\rangle\) 上的那个儿子。

容易发现这个过程和树剖很相似，因此如果 \(u\) 为重链的底部，则复杂度可以保证在 \(\mathcal{O}(d)\)

考虑动态维护轻重链剖分。而每次加入一个点至多改变 \(\mathcal{O}(d)\) 个节点，因此可以直接暴力修改

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

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
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)(3e3 + 15))

vector<int> vec[N];
int n,mxdep,fa[N],ch[N][2],sz[N],dep[N],t[N];
void link(int u,int f) { fa[u] = f; ch[f][ch[f][0] ? 1 : 0] = u; }
int ask(int u,int v)
{
    cout << "? " << u << ' ' << v << endl;
    return cin >> v, v;
}
void update(int u)
{
    for(; u; u = fa[u])
    {
        int &l = ch[u][0], &r = ch[u][1]; ++sz[u];
        if(l && r && sz[l] < sz[r]) swap(l,r);
    }
}
void solve(int now)
{
    int i,r,cnt,u,dis,tmp;
    for(int v : vec[now])
        for(r = 1; ;r = t[i / 2], r = ch[r][1])
        {
            for(cnt = 0, u = r; u; u = ch[u][0]) t[cnt++] = u;
            if(cnt == 1) { link(v, t[0]); update(v); break; }
            dis = ask(t[--cnt], v); tmp = dep[v] - dep[r]; i = cnt + tmp - dis;
            if(dis + tmp - cnt == 2) { link(v, t[i / 2]); update(v); break; }
        }
}
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++) {
        up(mxdep, dep[i] = ask(1,i)), vec[dep[i]].push_back(i);
    }
    for(int i = 1; i <= mxdep; i++) solve(i);
    cout << "! ";
    for(int i = 2; i <= n; i++) cout << fa[i] << " \n"[i == n];
    return 0;
}