bzoj 4754 独特的树叶

Posted on | Views:

树 $hash$ .

  • 要判断树的同构,自然要用到 $hash$ .但 $hash$ 的方法很多,我们要选取一种 优美 的方式.比如说字符串中,进制 $hash$ 就很优美,它可以 $O(1)$ 计算一个子串的 $hash$ 值.
  • 在树中,一般是将一个点的 $hash$ 值设为所有儿子 $hash$ 值从小到大排序组成的串的进制 $hash$ 值,再乘上这个点的子树大小.若为叶子节点,则 $hash$ 值为 $1$ .
  • 上面是对有根树的操作.然而这道题是无根树.找重心转成有根树十分麻烦(因为多了一个点),考虑换根,求出以每个点作为根节点的 $hash$ 值.
  • 设 $f(i),g(i),h(i)$ 分别表示以 $1$ 为根时节点 $i$ 的 $hash$ 值,以 $fa_i$ 为根并去掉子树 $i$ 后 $fa_i$ 的 $hash$ 值,以 $i$ 为根时节点 $i$ 的 $hash$ 值.
  • 对 $A,B$ 两棵树都做一次 $hash$ ,将 $A$ 中每个节点的 $h(i)$ 放入 $set$ 中,然后从小到大枚举 $B$ 树中度数为 $1$ 的点 $x$ .如果它连在 $y$ 上,由于我们 优美 的 $hash$ 定义,删去它后以 $y$ 为根, $y$ 的 $hash$ 值应该是 $\frac {h(x)} {n+1}$ .在 $set$ 中查询是否出现即可.
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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
typedef pair<int,int> pii;
#define mp make_pair
const int MAXN=1e5+10;
const int P=998244353;
inline int add(int a,int b)
{
	return (a + b >= P)? (a + b - P) : (a + b); 
}
inline int mul(int a,int b)
{
	return 1LL * a * b % P;
}
int fpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}
int Pow[MAXN],Base=37,val[MAXN];
int pre[MAXN],suf[MAXN];
pii vp[MAXN];
set<int> s;
struct Tree
{
	int n;
	int ecnt,head[MAXN],to[MAXN<<1],nx[MAXN<<1];
	int f[MAXN],g[MAXN],h[MAXN],siz[MAXN];
	int deg[MAXN];
	void addedge(int u,int v)
	{
		++ecnt;
		to[ecnt]=v;
		nx[ecnt]=head[u];
		head[u]=ecnt;
	}
	void init()
	{
		ecnt=0;
		for(int i=1;i<=n;++i)
			head[i]=f[i]=g[i]=h[i]=deg[i]=0;
		for(int i=1;i<n;++i)
		{
			int u=read(),v=read();
			addedge(u,v);
			addedge(v,u);
			++deg[u],++deg[v];
		}
	}
	void dfs1(int u,int fa)
	{
		siz[u]=1;
		int tot=0;
		for(int i=head[u];i;i=nx[i])
		{
			int v=to[i];
			if(v==fa)
				continue;
			dfs1(v,u);
			siz[u]+=siz[v];
		}
		for(int i=head[u];i;i=nx[i])
		{
			int v=to[i];
			if(v!=fa)
				val[++tot]=f[v];
		}
		sort(val+1,val+1+tot);
		int tmp=1;
		for(int i=1;i<=tot;++i)
		{
			f[u]=add(f[u],mul(tmp,val[i]));
			tmp=mul(tmp,Base);
		}
		f[u]=mul(f[u],siz[u]);
		if(!tot)
			f[u]=1;
	}
	void dfs2(int u,int fa)
	{
		int tot=0;
		for(int i=head[u];i;i=nx[i])
		{
			int v=to[i];
			if(v==fa)
				continue;
			vp[++tot]=mp(f[v],v);
		}
		if(fa)
			vp[++tot]=mp(g[u],-1);
		sort(vp+1,vp+1+tot);
		pre[0]=suf[tot+1]=0;
		for(int i=1;i<tot;++i)
			pre[i]=add(pre[i-1],mul(Pow[i-1],vp[i].first));
		for(int i=tot;i>1;--i)
			suf[i]=add(suf[i+1],mul(Pow[i-2],vp[i].first));
		for(int i=1;i<=tot;++i)
		{
			if(vp[i].second==-1)
				continue;
			g[vp[i].second]=mul(n-siz[vp[i].second],pre[i-1]+suf[i+1]);
		}
		if(!fa && tot==1)
			g[vp[1].second]=1;
		int tmp=1;
		for(int i=1;i<=tot;++i)
		{
			h[u]=add(h[u],mul(vp[i].first,tmp));
			tmp=mul(tmp,Base);
		}
		h[u]=mul(h[u],n);
		for(int i=head[u];i;i=nx[i])
		{
			int v=to[i];
			if(v!=fa)
				dfs2(v,u);
		}
	}
	void solve(int id)
	{
		dfs1(1,0);
		dfs2(1,0);
		if(!id)
		{
			for(int i=1;i<=n;++i)
				s.insert(h[i]);
		}
		else
		{
			int inv=fpow(n,P-2);
			for(int i=1;i<=n;++i)
			{
				if(deg[i]!=1)
					continue;
				int tmp=mul(h[i],inv);
				if(s.find(tmp)!=s.end())
				{
					cout<<i<<endl;
					return;
				}
			}
		}
	}
}A,B;
int main()
{
	int n=read();
	Pow[0]=1;
	for(int i=1;i<=n+1;++i)
		Pow[i]=mul(Pow[i-1],Base);
	A.n=n,B.n=n+1;
	A.init();
	B.init();
	A.solve(0);
	B.solve(1);
	return 0;
}