题目大意：
给定一棵树，这两棵树肯定是同构的。
问你，第一棵树的每个节点，可以对应第二个树的那个节点。 显然对应方法不唯一，SPJ来检测结果正确。
方法：
首先找树的重心， 树的重心最多2个。
一个重心的情况很多，两个重心的情况如图：
有人说这个图太对称了……
那给个不对称的。
这个图很重要……涉及到一些奇怪的情况
求树的重心，是一个简单的tree dp
f[i]表示i如果为根（为整棵树的根的情况下），所有儿子节点的size的max。
s[i]表示在做DP中，i的所有儿子的节点总数。
f[i] = max(s[j], n-sum(s[j])-1) 其中j为i的儿子。
然后找f[]数组中元素的最小值，就是树的重心了。
如果第一棵树的重心为A,B。 第二颗数的重心是C,D
那么就检查以A为根，以C为根的两棵树是否同构，再检查（A,D）,（B,C),(B,D）是否同构。同构则相对着输出即可。
题解这里判断同构的是给树进行哈希。给的方案是：
（我理解的……）
照抄题解“
这里提供一种方法：首先求解树的中点，然后将中点作为根。只有一个结点的子树哈希值为 1。选一个比较大的质数P和一个特别大的质数Q。对于每一颗树，把它的所有子树的哈希 值排序。然后hash=sum(P^{i}*hash[i])\%Qhash=sum(Pi∗hash[i])%Q，就能算出来总体的哈希值。有两个中点的树两个 中点都试一下。为了保险可以检查下哈希值有没有重的。
”
叶子节点的哈希值为1，假设要求K节点的哈希值。
K有儿子节点A,B,C。并且A<=B<=C（排序好了）
//求哈希值的方法！！！！
hash[k] = (P^1*hash[A])+ (P^2*hash[B])+(P^3*hash[C]) % Q；
hash=sum(P^{i}*hash[i])\%Qhash=sum(Pi∗hash[i])%Q；
P，Q为素数。
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<cmath> #include<vector> #include<map> #include<set> using namespace std; typedef long long ll; const ll pp[]={435617,999983,327827,674249,986191}; const ll mod=1e9+7; int n; ll cnt; map<string,ll> mapp; string s1[100010],s2[100010]; vector<ll> g1[100010],g2[100010]; ll Pow(ll a,ll b,ll M) { ll ans=1; a=a%M; while(b) { if(b&1) ans=ans*a%M; a=a*a%M; b/=2; } return ans; } ll get(char a[]) { string x=""; for(int i=0;a[i]!=0;x+=a[i++]); //cout<<x; if(mapp.find(x)==mapp.end()) { mapp[x]=++cnt; } else return mapp[x]; return cnt; } void init() { cnt=0; mapp.clear(); for(int i=0;i<=n;i++) { g1[i].clear(); g2[i].clear(); } char a[102],b[102]; for(int i=1;i<n;i++) { scanf("%s%s",a,b); ll A=get(a); s1[A]=a; ll B=get(b); s1[B]=b; g1[A].push_back(B); g1[B].push_back(A); // printf("%lld %lld\n",A,B); } for(int i=1;i<n;i++) { scanf("%s%s",a,b); ll A=get(a); s2[A]=a; ll B=get(b); s2[B]=b; g2[A].push_back(B); g2[B].push_back(A); //printf("%lld %lld\n",A,B); } } ll dp(int now,vector<ll> g[],ll f[],int father) { ll sum=0; f[now]=0; if(g[now].size()==0) { return 1; } for(int i=0;i<g[now].size();i++) { int v=g[now][i]; if(v!=father) { ll t=dp(v,g,f,now); sum+=t; f[now]=max(f[now],t); } } if(now!=father) f[now]=max(f[now],n-sum-1); return sum+1; } ll f1[100010],f2[100010]; ll f3[100010]; vector<ll> zhong1,zhong2; struct node { ll Hash,id; node(){} node(ll h,ll i) { Hash=h; id=i; } }; bool operator <(node a,node b) { return a.Hash<b.Hash; } vector<node> tmp[100010]; vector<ll> g3[100010],g4[100010]; ll myhash(int now,vector<ll> g[],ll f[],int fa,vector<ll> h[]) { //cout<<"Dsdsd"; if(g[now].size()==1&&g[now][0]==fa) { return f[now]=1; } ll hash_=0; tmp[now].clear(); for(int i=0;i<g[now].size();i++) { int v=g[now][i]; if(v!=fa) { ll t=myhash(v,g,f,now,h); tmp[now].push_back(node(t,v)); } } sort(tmp[now].begin(),tmp[now].end()); for(int i=0;i<tmp[now].size();i++) { h[now].push_back(tmp[now][i].id); hash_=(hash_+(tmp[now][i].Hash*Pow(pp[i%5],i+1,mod)))%mod; } f[now]=hash_; return f[now]; } void print(int a,int b) { // printf("fsfsf"); printf("%s %s\n",s1[a].c_str(),s2[b].c_str()); for(int i=0;i<g3[a].size();i++) { print(g3[a][i],g4[b][i]); } } bool check(int a,int b) { //cout<<"dsds"; for(int i=0;i<=n;i++) { g3[i].clear(); g4[i].clear(); } myhash(a,g1,f1,0,g3); myhash(b,g2,f2,0,g4); if(f1[a]==f2[b]) { print(a,b); return true; } return false; } void solve() { /* 第一步，求树的重心 */ dp(1,g1,f1,1); dp(1,g2,f2,1); // for(int i=1;i<=n;i++) // { // printf("f2[%d]==%d\n",i,f2[i]); // } zhong1.clear(); zhong2.clear(); memmove(f3,f1,sizeof(f3)); sort(f3+1,f3+1+n); ll tmp=f3[1]; for(int i=1;i<=n;i++) { // cout<<f1[i]<<tmp<<f2[i]<<endl; if(f1[i]==tmp) zhong1.push_back(i); if(f2[i]==tmp) zhong2.push_back(i); } for(int i=0;i<zhong1.size();i++) for(int j=0;j<zhong2.size();j++) if(check(zhong1[i],zhong2[j])) return; } int main() { while(scanf("%d",&n)!=EOF) { init();//存树 solve(); } return 0; }
我上面图上的那个情况，按照我理解的题解的做法，不管你素数取多少，都会重复。导致不管选哪一对重心，都会导致哈希值相同……
然后我给哈希函数改一下，排序好的A,B,C.... 并不都用P这一个素数，每5个数字循环一次，用5个素数来
//最稳定！！（保证不要重复）
hash[k] = (P[1]^1*hash[A])+ (P[2]^2*hash[B])+(P[3]^3*hash[C]) + ....+ [P[I%5+1]^I * hash[?]] % Q
这样…… 然后就AC了。
