自动搬运

查看原文

来自洛谷，原作者为

	lyx128 Who am I?

搬运于2025-08-24 22:06:30，当前版本为作者最后更新于2025-08-18 20:25:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

本题目考虑使用 map 实现，对于一个无根树，我们考虑找到它的重心（可能有两个），用重心作为新的根，将每棵子树的子节点值保存到 vector 并存到 map 当中，这样不会有哈希的冲突问题，最后比较新根值是否有相同，即有没有树同构。

代码也很简单，示例如下：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=50;
const int oo=2e9;
int T;
int n;
int u;
struct Edge{
	int v;
	int next;
}e[(N<<1)+5];
int head[N+5],cnt;
int id[N+5],itot;

void add(int u,int v){
	e[++cnt].v=v;
	e[cnt].next=head[u];
	head[u]=cnt;
	return ;
}
int dp[N+5];
int sz[N+5];

void dfs(int x,int father){
	sz[x]=1;
	id[x]=++itot;
	for(int i=head[x];i;i=e[i].next){
		int v=e[i].v;
		if(v==father)
			continue;
		dfs(v,x);
		sz[x]+=sz[v];
		dp[x]=max(dp[x],sz[v]);
	}
	dp[x]=max(dp[x],n-sz[x]);
	return ;
}
int tot;
map<vector<int>,int> mp;
int lst[N+5];

int push(int x,int father){
	vector<int> a;
	for(int i=head[x];i;i=e[i].next)
		if(e[i].v!=father)
			a.push_back(push(e[i].v,x));
	sort(a.begin(),a.end());
	if(!mp[a])
		mp[a]=++tot;
	return mp[a];
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>T;
	for(int t=1;t<=T;t++){
		cin>>n;
		memset(head,0,sizeof(int)*(n+2));
		cnt=0;
		for(int i=1;i<=n;i++){
			cin>>u;
			if(u)
				add(i,u),add(u,i);
		}
		itot=0;
		memset(dp,0,sizeof(int)*(n+2));
		memset(sz,0,sizeof(int)*(n+2));	
		dfs(1,0);
		int minn=oo;
		for(int i=1;i<=n;i++)
			minn=min(dp[i],minn);
		int res=oo;
		for(int i=1;i<=n;i++)
			if(dp[i]==minn){
				int id=push(i,0);
				if(lst[id])
					res=min(lst[id],res);
				else
					lst[id]=t;
			}
		cout<<((res==oo)?t:res)<<"\n";
	}
	return 0;
}