自动搬运

查看原文

来自洛谷，原作者为

	Legitimity Will there be a happily-ever-after?

搬运于2025-08-24 22:31:24，当前版本为作者最后更新于2021-05-16 10:31:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

如果你直接把 P7595 的代码往这里一粘，你就可以获得 $30-50$ pts 的优秀分数

此做法来自月赛讲评。

看这题的数据，显然是需要一个 $O(n\log n)$ 的做法。

考虑一个 simple idea：如果 $dep_u=dep_v+1$ 且 $u$ 在 $v$ 的子树中，那么 $f_u=v$。

那么就有一个显然的做法：$n$ 次询问把 $dep$ 搞出来，然后从根节点向下递归处理每个节点，对于每个节点询问一次子树，这样做询问的量级在 $O(n^2)$ 左右（连弱化版都过不了）。

如何改进？对于 $v$ 节点，确定一个儿子 $u$。知道了 $v$ 节点的子树，又知道了 $v$ 其它儿子的子树，两者相减就可以得到 $u$ 的子树。这样做，每次可以省去一个儿子的子树的询问。

那么 $u$ 应该选哪个呢？显然应该选重儿子，在考虑树剖和 dsu on tree 里的推论，可以得到 $\sum siz_i-siz_{u_i}$ 的量级在 $O(n\log n)$（证明可以去看 oiwiki），完全二叉树时达到下界。那么如果能够知道每个节点的重儿子，那么就可以在 $O(n\log n)$ 内解决这个问题。

如何在一颗结构不明的树里找到每个节点的重儿子？随机的艺术。

我们随机一些点，根据定义，重儿子的子树最大，那么应该占随机出的点就应该更多。那么我们就把占随机点最多的儿子当成重儿子。

那么应该随机几个呢？通过实验发现，随机 $1$ 个表现十分优秀。

为什么？随机的艺术。

复杂度的退化主要来自与处理时把重儿子和轻儿子颠倒了，如果出题人想卡这样的做法，就必须将重儿子搞得尽量重，但随即 $\sum siz_i-siz_{u_i}$ 也会更小，所以实际表现也十分优秀。

代码：（$son$ 表示重儿子，$siz$ 表示子树大小，$sontree$ 表示子树）

#include<bits/stdc++.h>
using namespace std;
#define rg register
#define inf 0x3f3f3f3f
#define ll long long
inline int read(){
	rg int ret=0,f=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)){ret=ret*10+ch-48;ch=getchar();}
    return f?-ret:ret;
}
int n,u,dep[5005],siz[5005],sontree[5005][5005],son[5005]; 
int fa[5005];
bool vis[5005];
void dfs(int x){
	if(!siz[x]) return;
	int tmp=sontree[x][rand()%siz[x]+1],cnt=0;
	random_shuffle(sontree[x]+1,sontree[x]+siz[x]+1);
	for(rg int i=1;i<=siz[x];++i){
		if(dep[sontree[x][i]]!=dep[x]+1) continue;
		if(tmp==sontree[x][i]) u=0;
		else printf("? 1 %d %d\n",sontree[x][i],tmp),fflush(stdout),u=read();
		if(u==dep[tmp]-dep[sontree[x][i]]){
			son[x]=sontree[x][i];
			break;
		}
	}//找到重儿子。 
	memset(vis,0,sizeof(vis));
	for(rg int i=1;i<=siz[x];++i){
		if(dep[sontree[x][i]]==dep[x]+1&&sontree[x][i]!=son[x]){
			printf("? 2 %d\n",sontree[x][i]); fflush(stdout);
			siz[sontree[x][i]]=read()-1;
			int cntnow=0;
			for(rg int j=1;j<=siz[sontree[x][i]]+1;++j){
				u=read(); vis[u]=1;
				if(u!=sontree[x][i]) sontree[sontree[x][i]][++cntnow]=u;
			}
		}
	}//询问轻儿子的子树 
	for(rg int i=1;i<=siz[x];++i){
		if(!vis[sontree[x][i]]&&sontree[x][i]!=son[x]) 
			sontree[son[x]][++siz[son[x]]]=sontree[x][i];
	}//根据轻儿子的子树推出重儿子的子树。 
	for(rg int i=1;i<=siz[x];++i){
		if(dep[sontree[x][i]]==dep[x]+1){
			fa[sontree[x][i]]=x;
			dfs(sontree[x][i]);
		}
	}//递归处理。 
}
signed main(){
	n=read(); 
	for(rg int i=2;i<=n;++i){
		printf("? 1 1 %d\n",i); fflush(stdout);
		dep[i]=read(); sontree[1][++siz[1]]=i;
	} //处理深度。 
	dfs(1);
	printf("! ");
	for(rg int i=2;i<=n;++i) printf("%d ",fa[i]);
	puts("");
	fflush(stdout);
	return 0;
}