P7597

· · 题解

Solution

首先，我们可以用 n-1 次操作 1 确定每个点的深度。这样的好处是，我们进行第二次操作的时候，就可以从这么多子孙里面看出哪些是当前节点的儿子。

考虑我们要确定这个点所有儿子的新的子孙。一个 Trival 的想法是全部用操作 2 再来一遍。但是这样会被链的情形卡成 O(n^2) 次输出。

考虑事实上新的子孙的情况是原来子孙情况的一个划分。所以我们确定了很多个儿子的子孙情况，而剩下一个就可以不用查询就直接得到结果。也就是我们能省掉很多的询问。

那显然是有限省掉重儿子啊。但是我们比不知道子树的大小，输。

那就交给概率，随便在这么多儿子里面随一个点。如果目前整个子树的大小为 n，随机出来的点在新子树大小为 s 的子树内出现的概率是 \dfrac{s}{n}。于是你期望能省掉 \sum \dfrac{s^2}{n} 次询问，其中 \sum s = n。

于是在最劣情况下，你的期望询问次数有：

T(n) = \max_{\sum s = n} \{n - \sum \dfrac{s^2}{n} + \sum T(s)\}

可以证明，T(n) = O(n \log n)。

下面是我边想边写半个小时整出来的证明。

Warning：限于本人低劣的数学水平，下文可能存在错误。下文出现了大量的近似，因为我们只是研究一个渐进复杂度，没有必要算出具体数值（更何况这是基于随机数的期望的。）

使用数学归纳法。假设我们在计算 T(n) 的时候，已知所有的 T(m) = m \ln m，m < n。

为啥用 \ln？

因为后面求导好算。

构造 f(m) = \dfrac{-m^2}{n} + m \ln m。其一阶导函数为 f'(m) = \dfrac{-2m}{n} + \ln m + 1。二阶导函数为 f''(m) = \dfrac{-2}{n} + \dfrac{1}{m}。

我们发现，导函数的拐点为 \dfrac{n}{2}。而且考虑几个子树的大小中，不可能有多个大于 \dfrac{n}{2} 的。先研究当 \sum s_i = k 为定值且 s_i \le \dfrac{n}{2} 的情况。根据 优超不等式，我们知道，必定要让大的尽可能大，小的尽可能小。于是我们知道，当 k \le \dfrac{n}{2} 时，当 s_1 = k 其他为 0 的时候和最大。当 k \ge \dfrac{n}{2} 时，当 s_1 = \dfrac{n}{2} 且 s_2 = k - \dfrac{n}{2} 且其他为 0 的时候和最大。

考虑如果有一个 s_1 \ge \dfrac{n}{2} 的存在，那么必定可以把其他的调整为 s_2 = n-s_1，其他为 0。然后再考虑两个积分：\int_{\frac{n}{2}-v}^{\frac{n}{2}} (\dfrac{-2}{n} + \dfrac{1}{m}) \text{d} m 和 \int_{\frac{n}{2}}^{\frac{n}{2}+v} (\dfrac{-2}{n} + \dfrac{1}{m}) \text{d} m

很容易发现，前者严格大于后者。也就是说，f(\dfrac{n}{2}) - f(n-s_1) \ge f(s_1) - f(\dfrac{n}{2})。这么说来，我们把 s_1 和 n-s_1 调整成两个 \dfrac{n}{2} 会更大。

因此我们就简化为：

T(n) = \dfrac{1}{2} n + 2T(\frac{n}{2})

根据主定理，T(n) = O(n \log n)。

也许，是对的？

还是放一下代码吧。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=5000+10;
int n,dep[MAXN],fa[MAXN],flg[MAXN];
vector<int> son[MAXN];
int query_dis(int u,int v) {
    cout<<"? "<<1<<' '<<u<<' '<<v<<endl;
    int ans; cin>>ans;
    return ans; 
}
vector<int> query_sons(int u) {
    cout<<"? "<<2<<' '<<u<<endl;
    vector<int> S; int cnt;
    cin>>cnt;
    ffor(i,1,cnt) {
        int id; cin>>id;
        if(id!=u) S.push_back(id);  
    }
    return S;
}
mt19937 myrand(time(0));
void solve(int u) {
    if(!son[u].size()) return ;
    vector<int> dson;
    for(auto id:son[u]) if(dep[id]==dep[u]+1) dson.push_back(id),fa[id]=u;
    int rnd=son[u][myrand()%son[u].size()],hson=-1;
    for(auto id:dson) if(rnd==id||(query_dis(rnd,id)==dep[rnd]-dep[id])) hson=id;
    memset(flg,0,sizeof(flg));
    for(auto id:dson) {
        if(id==hson) continue ;
        son[id]=query_sons(id);
        for(auto Id:son[id]) flg[Id]=1;
    }
    for(auto id:son[u]) if(dep[id]!=dep[u]+1&&!flg[id]) son[hson].push_back(id);
    son[u].clear();
    for(auto id:dson) solve(id);
    return ;
}
int main() {
    cin>>n;
    ffor(i,2,n) dep[i]=query_dis(1,i),son[1].push_back(i);
    solve(1);
    cout<<"! ";
    ffor(i,2,n) cout<<fa[i]<<' ';
    cout<<endl;
    return 0;
}