树哈希的板子,判断两个树是否有一种形态是相同的
#include <bits/stdc++.h>
#define inf 0x7fffffff
#define ll long long
//#define int long long
//#define double long double
#define re register int
#define void inline void
#define eps 1e-18
//#define mod 1e9+7
#define ls(p) p<<1
#define rs(p) p<<1|1
//#define ls(p) e[p].l
//#define rs(p) e[p].r
//#define pi acos(-1.0)
#define pb push_back
//#define P pair < int , int >
#define mk make_pair
#define fi first
#define se second
using namespace std;
const int mod=998244353;
const int M=1e8+5;
const int N=1e3+1;//?????????? 4e8.
ll ans[N][N];
int n,m,id;
namespace GP
{
struct node
{
int ver,next;
}e[N];
int tot,head[N];
void init()
{
for(re i=0;i<=n+1;i++) head[i]=0;
tot=1;
}
void add(int x,int y)
{
e[++tot].ver=y;
e[tot].next=head[x];
head[x]=tot;
}
void addedge(int x,int y)
{
add(x,y);add(y,x);
}
ll dfs(int x,int pre)
{
ll a[N];
ll ans=1ll*N,top=0;
for(re i=head[x];i;i=e[i].next)
{
int y=e[i].ver;
if(y==pre) continue;
a[++top]=dfs(y,x);
}
sort(a+1,a+top+1);
for(re i=1;i<=top;i++) ans=ans*2333+a[i];
return ans*2333+N+1;
}
}
void solve()
{
id++;
cin>>n;
GP::init();
for(re i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
if(x!=0) GP::addedge(x,i);
}
for(re i=1;i<=n;i++) ans[id][i]=GP::dfs(i,0);
sort(ans[id]+1,ans[id]+n+1);
for(re j=1,k=0;j<=id;j++)
{
while(k<=n) if(ans[id][++k]!=ans[j][k]) break;
if(k>n)
{
printf("%d\n",j);
break;
}
}
}
signed main()
{
// freopen("P1505_1.txt", "r", stdin);
// freopen("Aout.txt", "w", stdout);
int T=1;
cin>>T;
for(int index=1;index<=T;index++)
{
// printf("Case #%lld: ",index);
solve();
// puts("");
}
return 0;
}
/* 10 5 hbtngdflmj 1 10 1 2 9 0 3 8 1 4 7 0 5 6 1 */
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/35446.html