隐藏
「2015四校联考-nodgd」仔细的检查 - 无根树的同构 | Bill Yang's Blog
0%

「2015四校联考-nodgd」仔细的检查 - 无根树的同构

题目大意

给两棵无根树,判断是否同构。
若同构,输出第一棵树$i$结点在第二棵树对应的编号。


吐槽

这道题啊,没有spj就别做了吧
今天考这道题,居然写出了正解又改错了…
然而当我觉得改一点地方就能A的时候,我就调了一个下午,整整两页的WA,哇!
nkoj还没有spj,毒瘤nodgd还故意卡hash,感觉人生已经绝望。


初步想法

判断有根树同构我们有四种方法:

  • 树的括号表示法
  • 按照儿子深度最小表示法比较(少用)
  • 按照儿子Size最小表示法的hash比较
  • prufer编码

而此题是无根树,那么必须转为有根树解决。
枚举根?效率太低,有没有其他的方法?
考虑哪些根是比较特殊的,那么两棵树就可以采用这些特殊点来作为根。
①树的中心(树的直径中心点)
②树的重心
似乎nodgd标解使用的是方法①,那么我就来写写方法②吧。
众所周知,重心最多两个,且这两个重心必定相邻。(什么你不知道,请参考度娘)
这样我们就可以在枚举常数级别的根的情况下将无根树转为有根树。
定义:将树中每个结点的儿子按照其最小表示排序后所得到的树为该树的最小表示,单个结点的最小表示为其Size。(判断有根树同构方法3)
根据定义,我们可以分别得到两棵树的两个重心(只有一个重心略)。
那么我们用第二棵树的重心1、重心2分别与第一棵树的重心1比较,如果其中一个最小表示相同即可输出YES


构造最小表示

刚才我们基于已得到最小表示得出了算法流程,那么现在考虑如何求出最小表示。
设当前结点为$u$,其儿子为$son[]$,结点$i$子树大小为$Size[i]$,则:
为了保证最小表示,则将儿子按照最小表示排序,将$son[]$按照$Size[son[i]]$排序,若$Size[son[i]]$相同再比较$Hash[son[i]]$。
等等,刚刚我们提到了$Hash$?什么是$Hash$?
如果我们要比较子树的最小表示,那么需要递归子树$Size$,不就$O(n^2)$了?为了降低时间复杂度使用$Hash$来表示最小表示。
刚刚我们已经对儿子排好序了。
令$Hash[u]=Size[u]$,对于每一个儿子,$Hash[u]=Hash[u]*num+Hash[son[i]]$,$num$是随意选得一个数,别太大,最好是素数,我选的是99995999(因为9比较多),$Hash$可以模一个大素数,也可以像我一样选择自然溢出。


构造方案

判断出来了是否同构后,我们只需要构造一个合法方案即可。
我们可以采用Dfs序的方式,从重心开始,存下来每一棵树每个时间访问的结点$Dfn1[]$与$Dfn2[]$。
然后按照$Dfn1[]$为第一关键字排个序,$Dfn2[]$中的值即为答案。
当然如果你用桶我也不反对。


玄学

如果你仔细看完了上面的题解,那么恭喜你,你可以陷入和我一样的无限调试了。
如果你RE,请尝试开手工栈。(我们oj栈较大,不需要开)
如果你WA,请检查是否有数组为清空。
如果你死活错一个点,请参考下面:

  • 先用$Size$排序,若$Size$相同再排$Hash$
  • $Hash$函数用异或代替加法,即$Hash[u]=Hash[u]*num\quad xor\quad Hash[son[i]]$
    然而这样完全没有科学依据啊,为什么改了我就过了呢?因为nodgd是毒瘤啊~!!

代码

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef unsigned long long LL;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const LL maxn=500005;
LL Size[maxn],cnt=0,tot=0,Hash[maxn],Maxson[maxn],tmp[maxn],Dfn[maxn],First[maxn],a[maxn],Min=0x7fffffff/2,Min1,Min2,Hash1;
vector<int>edges[maxn];
bool cmp1(const int& a,const int& b) {
return Size[a]<Size[b]||(Size[a]==Size[b]&&Hash[a]<Hash[b]);
}
void Dfs1(int Now,int father) {
Size[Now]=1;
for(int i=0; i<edges[Now].size(); i++) {
int Next=edges[Now][i];
if(Next==father)continue;
Dfs1(Next,Now);
Size[Now]+=Size[Next];
}
cnt=0;
for(int i=0; i<edges[Now].size(); i++) {
int Next=edges[Now][i];
if(Next==father)continue;
a[++cnt]=Next;
}
sort(a+1,a+cnt+1,cmp1);
a[cnt+1]=father;
for(int i=0; i<edges[Now].size(); i++)edges[Now][i]=a[i+1];
Hash[Now]=Size[Now];
for(int i=0; i<edges[Now].size(); i++) {
int Next=edges[Now][i];
if(Next==father)continue;
Hash[Now]=Hash[Now]*99995999^Hash[Next];
}
}
void Dfs2(int Now,int father) {
Dfn[++tot]=Now;
for(int i=0; i<edges[Now].size(); i++) {
int Next=edges[Now][i];
if(Next==father)continue;
Dfs2(Next,Now);
}
}
int n;
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
void Find_Core(int Now,int father) {
Size[Now]=1;
for(int i=0; i<edges[Now].size(); i++) {
int Next=edges[Now][i];
if(Next==father)continue;
Find_Core(Next,Now);
Size[Now]+=Size[Next];
Maxson[Now]=max(Maxson[Now],Size[Next]);
}
Maxson[Now]=max(Maxson[Now],n-Size[Now]);
if(Maxson[Now]<Min) {
Min=Maxson[Now];
Min1=Now;
Min2=0;
} else if(Maxson[Now]==Min)Min2=Now;
}
void Clear() {
memset(Maxson,0,sizeof(Maxson));
Min=0x7fffffff/2;
Min1=Min2=0;
for(int i=1; i<=n; i++)edges[i].clear();
cnt=0;
memset(a,0,sizeof(a));
memset(Hash,0,sizeof(Hash));
}
struct Compare {
int x,y;
bool operator < (const Compare& b) const {
return x<b.x;
}
} cmp[maxn];
int main() {
n=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
AddEdge(y,x);
}
Find_Core(1,0);
Dfs1(Min1,0);
Dfs2(Min1,0);
Hash1=Hash[Min1];
for(int i=1; i<=n; i++)First[i]=Dfn[i];
Clear();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
AddEdge(y,x);
}
Find_Core(1,0);
Dfs1(Min1,0);
tot=0;
Dfs2(Min1,0);
if(Hash1==Hash[Min1]) {
for(int i=1; i<=n; i++)cmp[i].x=First[i],cmp[i].y=Dfn[i];
sort(cmp+1,cmp+n+1);
puts("YES");
for(int i=1; i<=n; i++)printf("%d ",cmp[i].y);
} else if(Min2) {
Dfs1(Min2,0);
tot=0;
Dfs2(Min2,0);
if(Hash1==Hash[Min2]) {
for(int i=1; i<=n; i++)cmp[i].x=First[i],cmp[i].y=Dfn[i];
sort(cmp+1,cmp+n+1);
puts("YES");
for(int i=1; i<=n; i++)printf("%d ",cmp[i].y);
} else puts("NO");
} else puts("NO");
return 0;
}
姥爷们赏瓶冰阔落吧~