題干：

樹是一種很常見的數據結構。

我們把N個點，N-1條邊的連通無向圖稱為樹。

若將某個點作為根，從根開始遍歷，則其它的點都有一個前驅，這個樹就成為有根樹。

對于兩個樹T1和T2，如果能夠把樹T1的所有點重新標號，使得樹T1和樹T2完全相

同，那么這兩個樹是同構的。也就是說，它們具有相同的形態。

現在，給你M個有根樹，請你把它們按同構關系分成若干個等價類。

Input

第一行，一個整數M。

接下來M行，每行包含若干個整數，表示一個樹。第一個整數N表示點數。接下來N

個整數，依次表示編號為1到N的每個點的父親結點的編號。根節點父親結點編號為0。

Output

輸出M行，每行一個整數，表示與每個樹同構的樹的最小編號。

Sample Input

4 4 0 1 1 2 4 2 0 2 3 4 0 1 1 1 4 0 1 2 3

Sample Output

1 1 3 1

Hint

【樣例解釋】?

編號為1, 2, 4 的樹是同構的。編號為3 的樹只與它自身同構。?

100% 的數據中，1 ≤ N, M ≤ 50。?

題目大意：

? 中文題意不解釋了。

解題報告：

? 直接轉化成無根樹然后扔到set中，然后對于每一個求ans的時候直接暴力判斷就好。所以對于每一棵樹都要隨便找一個點的Hash值當做代表值（這里用的是H[1]），再去set中判斷。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 55 + 5; const ll MOD = 2000004199; //用這個模數都沒有問題！ const ll seed = 13331;//可換！ ll INV; struct Edge {int v,ne; } e[MAX<<1]; int head[MAX],tot; int n,m; void adde(int u,int v) {e[++tot].v = v;e[tot].ne = head[u]; head[u] = tot; } inline ll qpow(ll a,ll b) {ll res = 1;while(b) {if(b&1) res = res * a % MOD;a = a *a % MOD;b >>= 1; }return res; } inline ll add(ll x,ll y) {return (x+y)%MOD;} inline ll mul(ll x,ll y) {return (x*y)%MOD;} inline ll sub(ll x,ll y) {return (x-y+MOD)%MOD;} ll H[MAX]; int size[MAX],du[MAX]; void dfs(int cur,int fa) {H[cur] = 1;size[cur] = 1;for(int i = head[cur]; ~i; i = e[i].ne) {int v = e[i].v;if(v == fa) continue;dfs(v,cur);size[cur] = add(size[cur],size[v]);H[cur] = mul(H[cur],H[v]);}H[cur] = add(H[cur],size[cur]);H[cur] = mul(H[cur],seed); } set<ll> ss[MAX]; void dfs1(int num,int cur,int fa) {ss[num].insert(H[cur]);//必須要先插入，因為根的情況。 ll Hall = mul(H[cur],INV),Hres;Hall = sub(Hall,n);for(int i = head[cur]; ~i; i = e[i].ne) {int v = e[i].v;if(v == fa) continue;Hres=mul(Hall,qpow(H[v],MOD-2));Hres=add(Hres,n-size[v]); Hres=mul(Hres,seed);//至此Hres代表除v的樹的Hash值H[v]=mul(H[v],INV); H[v]=sub(H[v],size[v]);H[v]=mul(H[v],Hres);H[v]=add(H[v],n);H[v]=mul(H[v],seed);dfs1(num,v,cur);} } void init() {tot=0;memset(head,-1,sizeof head); } ll ans[MAX]; int main() {INV = qpow(seed,MOD-2);cin>>m;for(int u,v,i = 1; i<=m; i++) {cin>>n;init();for(int j = 1; j<=n; j++) {cin>>u;if(u == 0) continue;adde(u,j);adde(j,u);}dfs(1,0);dfs1(i,1,0);ans[i] = H[1];}for(int i = 1; i<=m; i++) {for(int j = 1; j<=i; j++) {if(ss[j].count(ans[i])) {ans[i] = j;break;}}for(int i = 1; i<=m; i++) printf("%lld\n",ans[i]);return 0 ; }

?

總結

以上是生活随笔為你收集整理的【BZOJ - 4337】BJOI2015 树的同构（树哈希）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。