题目id 15793
题意
给定有 n 个节点的原无根树有和 n+1 个节点的新无根树
回答对于新无根树，变为原树需要删去哪一个编号最小的叶子结点
思路
-
用树哈希算出以每个节点为根的原树哈希值
-
按编号大小枚举新树叶子节点，计算删去此节点后哈希值
-
判断原树是否存在这样的哈希值，若存在则输出此节点编号
树哈希
对于以 i 为根的树，哈希值：
H_i=1+\sum_{j\in son_i} H_j * prim[siz[j]]
其中 prim[i] 表示第 i 个质数，因此本题筛质数时需要筛到 2*10^6
实现
对两颗树，计算出 H 后
使 Hash_1 = H_1 ，用换根 dp 计算 Hash_i : Hash_i=H_i +(Hash_{fat_i}-H_i*prim[siz[i]])*prim[totsiz-siz[i]]
将原树的 Hash_i 加入 map
按编号枚举新树节点 $i$，若节点度数为 1 则以 fat_i 为根的删后哈希值 hash=Hash_{fat_i}-Hash_i*prim[siz[i]] 即 hash=Hash_{fat_i}-2
在 map 中查找
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define ull unsigned long long
using namespace std;
const int N=1e5+100;
struct node{
int fr,to,ne;
}ed[2][N*2];
int he[2][N],n_e[2],n;
int siz[2][N],du[N],fat[N];
ull Hash[2][N],hasH[2][N];
int prim[N*20],len=0,bk[N*20];
map<ull,int>mp;
void add(int x,int y,int ty){
ed[ty][++n_e[ty]].fr=x;ed[ty][n_e[ty]].to=y;ed[ty][n_e[ty]].ne=he[ty][x];he[ty][x]=n_e[ty];
}
void dfs(int x,int fa,int ty){
Hash[ty][x]=1ull;
siz[ty][x]=1;
for(int i=he[ty][x];i!=-1;i=ed[ty][i].ne){
int y=ed[ty][i].to;
if(y==fa)continue;
dfs(y,x,ty);
siz[ty][x]+=siz[ty][y];
Hash[ty][x]+=Hash[ty][y]*(ull)prim[siz[ty][y]];
}
}
void dfs1(int x,int fa,int ty){
if(x!=1)hasH[ty][x]=Hash[ty][x]+(hasH[ty][fa]-Hash[ty][x]*(ull)prim[siz[ty][x]])*(ull)prim[n+ty-siz[ty][x]];
else hasH[ty][x]=Hash[ty][x];
for(int i=he[ty][x];i!=-1;i=ed[ty][i].ne){
int y=ed[ty][i].to;
if(y==fa)continue;
dfs1(y,x,ty);
}
}
void init(){
for(int i=2;i<=N*20-10;i++){
if(!bk[i])prim[++len]=i;
for(int j=1;j<=len&&prim[j]*i<=N*20-10;j++){
bk[i*prim[j]]=1;
if(i%prim[j]==0)break;
}
}
}
int main(){
init();
scanf("%d",&n);
for(int i=1;i<=n+1;i++)he[0][i]=he[1][i]=-1;
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y,0);add(y,x,0);
}
for(int i=1;i<=n;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y,1);add(y,x,1);
du[x]++;du[y]++;
fat[x]=y;fat[y]=x;
}
dfs(1,0,0);dfs(1,0,1);
dfs1(1,0,0);dfs1(1,0,1);
for(int i=1;i<=n;i++)mp[hasH[0][i]]=1;
for(int i=1;i<=n+1;i++)
if(du[i]==1){
ull ha=hasH[1][fat[i]]-2ull;
if(mp.find(ha)!=mp.end()){printf("%d\n",i);return 0;}
}
return 0;
}
双倍经验
洛谷 P4323 [JSOI2016] 独特的树叶