题意：给你两颗有根树，判定是否同构。
用了《Hash在信息学竞赛中的一类应用》中的哈希函数。
len就是某结点的子树大小，g是某结点的孩子数+1。
这个值也是可以动态转移的！具体见论文，所以能高速处理出一颗无根树以每个顶点为根时的哈希值。改日敲个板子试试。
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
typedef vector<int>::iterator ITER;
vector<int>G[2][3005];
const ull base=3001ll;
ull bs[3005],f[2][3005];
int T,n,n2,fa[3005],fa2[3005],siz[2][3005];
char a[3005],b[3005];
void df1(int op,int U){
siz[op][U]=1;
for(ITER it=G[op][U].begin();it!=G[op][U].end();++it){
df1(op,*it);
siz[op][U]+=siz[op][*it];
}
}
bool cm0(const int &a,const int &b){
return f[0][a]<f[0][b];
}
bool cm1(const int &a,const int &b){
return f[1][a]<f[1][b];
}
void dfs(int op,int U){
f[op][U]=(ull)(G[op][U].size()+1)*bs[siz[op][U]-1];
for(ITER it=G[op][U].begin();it!=G[op][U].end();++it){
dfs(op,*it);
}
if(op==0){
sort(G[op][U].begin(),G[op][U].end(),cm0);
}
else{
sort(G[op][U].begin(),G[op][U].end(),cm1);
}
int now=0;
for(ITER it=G[op][U].begin();it!=G[op][U].end();++it){
f[op][U]+=f[op][*it]*bs[now];
now+=siz[op][*it];
}
}
int main(){
bs[0]=1;
for(int i=1;i<=3000;++i){
bs[i]=bs[i-1]*base;
}
scanf("%d",&T);
for(;T;--T){
memset(fa,0,sizeof(fa));
memset(fa2,0,sizeof(fa2));
memset(f,0,sizeof(f));
memset(siz,0,sizeof(siz));
for(int i=1;i<=n;++i){
G[0][i].clear();
}
for(int i=1;i<=n2;++i){
G[1][i].clear();
}
n=n2=1;
scanf("%s%s",a+1,b+1);
int len=strlen(a+1);
int U=1;
for(int i=1;i<=len;++i){
if(a[i]=='0'){
G[0][U].push_back(++n);
fa[n]=U;
U=n;
}
else{
U=fa[U];
}
}
U=1;
for(int i=1;i<=len;++i){
if(b[i]=='0'){
G[1][U].push_back(++n2);
fa2[n2]=U;
U=n2;
}
else{
U=fa2[U];
}
}
if(n!=n2){
puts("different");
continue;
}
for(int i=0;i<2;++i){
df1(i,1);
dfs(i,1);
}
puts(f[0][1]==f[1][1] ? "same" : "different");
}
return 0;
}