[TIOJ] 1214. 樹論 之 樹同構測試 (Hash)

題目連結:http://tioj.infor.org/problems/1214

---

原本以為可以拿個中序前序之類的來判，但感覺還是慘慘的。後來才知道原來其實可以把一整棵樹的形狀hash起來，這樣的話就可以直接看hash值來判了，不過要怎麼hash呢?這裡的作法是先定義葉節點的hash值，而其他非葉節點則將他所有子樹的hash值平方後加起來，這樣只要根一樣的話那hash出來的值就會一樣(但有可能有碰撞)，但是這題給的是棵無根樹，若沒有用一些好方法定根，那hash出來的值就很有可能不一樣，這裡利用樹的一個特殊的性質－一顆樹的重心最多只有兩顆，所以用重心當根判一下就可以有$O(n)$的複雜度了。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long llu;
#define FF first
#define SS second
#define PB push_back
#define ALL(x) (x).begin(), (x).end()
const int N = 100 + 5;
const int mod = 44478311;

vector<int> G1[N], G2[N];
int sz1[N], sz2[N];

inline void init(int);
int GetCentroid(vector<int>[],int[],int,int,int);
llu Hash(vector<int>[],int,int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	while(cin>>n, n){
		init(n);
		for(int i=0;i<n-1;i++){
			int u, v; cin>>u>>v;
			G1[u].PB(v);
			G1[v].PB(u);
		}
		for(int i=0;i<n-1;i++){
			int u, v; cin>>u>>v;
			G2[u].PB(v);
			G2[v].PB(u);
		}
		int cen1 = 1;
		GetCentroid(G1, sz1, 1, 1, n);
		for(int i=1;i<=n;i++) if(sz1[cen1] > sz1[i]) 
			cen1 = i;
		GetCentroid(G2, sz2, 1, 1, n);
		int cen2 = 1;
		for(int i=1;i<=n;i++) if(sz2[cen2] > sz2[i]) 
			cen2 = i;
		int cen22 = cen2;
		for(int i=1;i<=n;i++) if(sz2[cen22] >= sz2[i]) 
			cen22 = i;
		llu hh1 = Hash(G1, cen1, cen1);
		llu hh2 = Hash(G2, cen2, cen2);
		if(hh1 == hh2){
			cout<<"Same\n";
			continue;
		}
		hh2 = Hash(G2, cen22, cen22);
		if(hh1 == hh2) cout<<"Same\n";
		else cout<<"Different\n";
	}
	return 0;
}

inline void init(int n){
	for(int i=1;i<=n;i++){
		G1[i].clear();
		G2[i].clear();
	}
}

int GetCentroid(vector<int> G[], int sz[], int w ,int f, int n){
	int cnt = 1, mx = 0;
	for(auto i: G[w]){
		if(i==f) continue;
		int tp = GetCentroid(G, sz, i, w, n);
		mx = max(tp, mx);
		cnt+=tp;
	}
	mx = max(n-cnt, mx);
	sz[w]=mx;
	return cnt;
}

llu Hash(vector<int> G[], int w, int f){
	llu r = 139;
	for(auto i:G[w]){
		if(i==f) continue;
		llu haha = Hash(G, i, w);
		r = (r + (haha*haha)%mod)%mod;
	}
	return r;
}