题解：P7595 「EZEC-8」猜树

dyc2022 · 2025-09-24 17:48:01 · 题解

更好的阅读体验

Update 2025/10/04：修改了一处笔误。

我们考虑如何确定一个点 v 是否是 u 的儿子。

• 如果我们已经确定了 v 的深度为 u 的深度 +1，那么我们只需要检查 u, v 的距离是否为 1。如果距离为 1 就说明有边相连。
• 如果我们已经确定了 v 在 u 的子树中，那么只需要检查 v 的深度是否为 u 的深度 +1。

后文中“查询次数”为输入的数字个数。假设树上深度为 i 的节点个数有 p_i 个，i 子树的大小为 s_i。不难发现，第一种方法的查询次数为 p_ip_{i+1}，第二种方法的查询次数是 s_i。

我们考虑根号分治。设置阈值 B，对于深度为 i 的节点，如果 s_i < B，层内的节点数量不会太多，则我们跑第一个过程；否则这样的层的数量不会太多，跑第二个过程。

所以查询次数为 O(n \sqrt n)，可以通过。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 2006
using namespace std;
int n,B,dep[N],fa[N];
vector<int> p[N];
int query1(int u,int v)
{
    printf("? 1 %lld %lld\n",u,v),fflush(stdout);
    return scanf("%lld",&u),u;
}
vector<int> query2(int u)
{
    int sz;vector<int> vec;
    printf("? 2 %lld\n",u),fflush(stdout);
    scanf("%lld",&sz),vec.resize(sz);
    for(int i=0;i<sz;i++)scanf("%lld",&vec[i]);
    return vec;
}
main()
{
    scanf("%lld",&n);
    B=pow(n,0.5),p[dep[1]=1].push_back(1);
    for(int i=2;i<=n;i++)
        dep[i]=query1(1,i)+1,p[dep[i]].push_back(i);
    for(int i=1;i<=n;i++)if(p[i].size())
    {
        if(p[i].size()<B)
        {
            for(int u:p[i])for(int v:p[i+1])
                if(query1(u,v)==1)fa[v]=u;
        } else {
            for(int u:p[i])
            {
                vector<int> t=query2(u);
                for(int v:t)if(dep[v]==dep[u]+1)fa[v]=u;
            }
        }
    }
    putchar('!');
    for(int i=2;i<=n;i++)printf(" %lld",fa[i]);
    putchar(10),fflush(stdout);
    return 0;
}