BZOJ 4337 树的同构

发表于 | 更新于

Link

Solution

树的哈希什么的感觉还是很有意思呢 数据太小估计怎么搞搞都能过。。 另外有一个惊人的事实是一个树至多有22个重心。画个图似乎确实是的样子。。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include "lucida"
using std::map;
using std::sort;
using std::pair;
typedef unsigned long long qword;
const int MAXN=60,INF=0x1f1f1f1f;
qword p3[MAXN];
struct _{_() {
	p3[0]=1;
	for(int i=1;i<MAXN;++i) {
		p3[i]=p3[i-1]*3;
	}
}}Auto;
struct Edge {
	int to;Edge *pre;
	Edge(int to,Edge *pre):to(to),pre(pre) {}
	void *operator new(size_t) {
		static Edge *Me=alloc(Edge,MAXN*MAXN<<1);
		return Me++;
	}
};
struct Tree {
	int n;Edge *G[MAXN];
	void Adde(int f,int t) {
		G[f]=new Edge(t,G[f]);
		G[t]=new Edge(f,G[t]);
	}
	void operator () (int f,int t) {
		Adde(f,t);
	}
	int sz[MAXN],f[MAXN];
	void preDFS(int pos,int from) {
		sz[pos]=1;
		for(Edge *e=G[pos];e;e=e->pre) {
			if(e->to!=from) {
				int u=e->to;
				preDFS(u,pos);
				chkmx(f[pos],sz[u]);
				sz[pos]+=sz[u];
			}
		}
		chkmx(f[pos],n-sz[pos]);
	}
	pair<qword,int> Pool[MAXN][MAXN];
	qword DFS(int pos,int from) {
		pair<qword,int> *sh=Pool[pos];qword hash=1;
		int sc=0;sz[pos]=1;
		for(Edge *e=G[pos];e;e=e->pre) {
			if(e->to!=from) {
				int u=e->to;
				sh[++sc]=pair<qword,int>(DFS(u,pos),sz[u]);
				sz[pos]+=sz[u];
			}
		}
		sort(sh+1,sh+1+sc);
		for(int i=1;i<=sc;++i) {
			(hash*=p3[sh[i].second+1])+=sh[i].first;
		}
		(hash*=3)+=2;
		return hash;
	}
	qword Hash() {
		preDFS(1,0);
		static int gc[MAXN],gcc;
		f[gc[gcc=0]=0]=INF;
		for(int i=1;i<=n;++i) {
			if(f[i]<f[gc[1]]) {
				gc[gcc=1]=i;
			} else if(f[i]==f[gc[1]]) {
				gc[++gcc]=i;
			}
		}
		assert(gcc<=2);
		qword res=0;
		for(int i=1;i<=gcc;++i) {
			chkmx(res,DFS(gc[i],0));
		}
		return res;
	}
}tr[MAXN];
int main() {
	freopen("input","r",stdin);		
	map<qword,int> record;
	int m;is>>m;
	for(int i=1;i<=m;++i) {
		is>>tr[i].n;
		for(int j=1;j<=tr[i].n;++j) {
			int fa;is>>fa;
			if(fa) tr[i](fa,j);
		}
		qword hash=tr[i].Hash();
		if(!record.count(hash)) {
			record[hash]=i;
		}
		os<<record[hash]<<'\n';
	}
	return 0;
}