P4323
princessyyx
·
·
题解
题目大意
有两棵树 A 和 B。树 A 有 N 个点，编号为 1 到 N；树 B 有 N+1 个节点，编号为 1 到 N+1。
树 B 恰好是由树 A 加上一个叶子节点，然后将节点的编号打乱后得到的。
求这个多余的叶子的编号。
解题思路
树哈希 + 换根 DP + set。
树哈希
根据题意，判断一些树是否同构的时，我们常常把这些树转成哈希值储存起来，以降低复杂度。
树哈希是很灵活的，可以设计出各种各样的哈希方式；但是如果随意设计，很有可能是错误的，容易被卡。
树哈希的方法有很多种，可以参考 OI WIKI 上的博客。
以下介绍一类国家集训队奆老发明的容易实现且（目前）没有被卡掉的哈希编码方式。
定义哈希数组 Hash1_u 求出以 u 为根的子树的哈希值，编码方式为：
Hash1_u=\sum\limits Hash1_v \times P_{siz_v}
但以每个节点为根跑一遍 ```DFS``` 求哈希，时间复杂度为 $\Theta(n^2)$ 会超时。
### 换根 DP
定义以 $v$ 为根时整棵树的哈希值为 $Hash2_v$。
显然的，我们可以通过 $Hash1$ 推导 $Hash2$ 的值：
```hash2[u]=hash1[u]+tmp*prm[n-siz[u]];```
这样将求哈希的过程优化到 $\Theta(n)$。
具体实现看代码。
## AC 代码（附有注释）
```cpp
#include <iostream>
#include <string.h>
#include <set>
#define int unsigned long long
//哈希自然溢出
using namespace std;
struct node{int to,nxt;}e[114514<<1];
int head[114514<<1],tot;//双向边
void add(int x,int y){
e[++tot]={y,head[x]};
head[x]=tot;
}
int prm[1919810<<1];
bool isp[1919810<<1];
void init(int x){
memset(isp,1,sizeof isp);
prm[0]=0;
for(register int i=2; i<=x; i++){
if (isp[i])prm[++prm[0]]=i;
for(int j=1; j<=prm[0]&&i*prm[j]<=x; j++){
isp[i*prm[j]]=0;
if (!(i%prm[j])) break;
}
}//初始化筛质数
}
int n,siz[114514],deg[114514];
int hash1[114514],hash2[114514];
void dfs1(int u,int fa){
siz[u]=hash1[u]=1;
for(register int i=head[u]; i; i=e[i].nxt){
int to=e[i].to;
if(to==fa) continue;
dfs1(to,u);
siz[u]+=siz[to];
hash1[u]+=hash1[to]*prm[siz[to]];
}
}//dfs1求Hash1
void dfs2(int u,int fa,int tmp){
hash2[u]=hash1[u]+tmp*prm[n-siz[u]];
for(int i=head[u]; i; i=e[i].nxt){
int to=e[i].to;
if(to==fa) continue;
dfs2(to,u,hash2[u]-hash1[to]*prm[siz[to]]);
}
}//dfs2求Hash2
set<int> s;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n;
init(1299710);//第 1e5 个质数
int jj,fq;
for(register int i=1; i<n; i++){
cin >> jj >> fq;
add(jj,fq);add(fq,jj);
}//建树A
dfs1(1,0);dfs2(1,0,0);
for(register int i=1; i<n; i++)
s.insert(hash2[i]);//用set记录A的哈希值，以便logn查询。
memset(head,0,sizeof head);tot=0;
n++;//B节点数为n+1
for(register int i=1;i<n;i++){
cin >> jj >> fq;
add(jj,fq);add(fq,jj);//建树B
deg[jj]++,deg[fq]++;//记录节点度数
}
dfs1(1,0);dfs2(1,0,0);
for(register int i=1; i<=n; i++){
if(deg[i]!=1) continue;//不是叶子
if(s.find(hash2[e[head[i]].to]-2)!=s.end()){
cout << i << endl;//与A同构
return 0;
}
}
}
```