标签：hash，树

题目

题目传送门

Description

JYY有两棵树A和B：树A有N个点，编号为1到N；树B有N+1个点，编号为1到N+1。JYY知道树B恰好是由树A加上一个叶节点，然后将节点的编号打乱后得到的。他想知道，这个多余的叶子到底是树B中的哪一个叶节点呢？

Input

输入一行包含一个正整数N。

接下来N-1行，描述树A，每行包含两个整数表示树A中的一条边；

接下来N行，描述树B，每行包含两个整数表示树B中的一条边。

1≤N≤10^5

Output

输出一行一个整数，表示树B中相比树A多余的那个叶子的编号。

如果有多个符合要求的叶子，输出B中编号最小的那一个的编号

Sample Input

Sample Output

题意

给定两棵树，分别有N和N+1个节点，要你找出第二棵树比第一棵树多的那一个节点，编号尽量小

分析

前置技能：树的同构

先求一个树的hash，我就异或+乱搞，然后把这棵树的所有hash值放入map中，再对于另一棵树的每个hash值看看map里面有没有对应的

这题需要换根操作把所有hash值快速求出，对于新的树，答案肯定是度数为1的节点，可以把当前度数为1的点删除后看map里是否有相同的hash值，取最小值

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{ll f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
const int maxn=1e5+6,pri=1e9+7;
map<ll,bool>s;
ll hash[maxn];
struct edge{
   int to,next;}e[maxn<<1];
int c[maxn],size[maxn],n,ans=0x7fffffff,cnt,last[maxn];
void insert(int u,int v){e[++cnt]=(edge){v,last[u]};last[u]=cnt;e[++cnt]=(edge){u,last[v]};last[v]=cnt;
}
void build(int x,int fa){size[x]=1;reg(x){if(e[i].to==fa)continue;build(e[i].to,x);hash[x]=hash[x] ^ (hash[e[i].to]+29);size[x]+=size[e[i].to];}hash[x]+=size[x]*pri+1;
}
void dfs(int x,int fa){s[hash[x]]=1;reg(x){if(e[i].to==fa)continue;ll temp=((hash[x]-n*pri-1)^(hash[e[i].to]+29))+(n-size[e[i].to])*pri+1;hash[e[i].to]=((hash[e[i].to]-pri*size[e[i].to]-1)^(temp+29))+n*pri+1;size[e[i].to]=n;dfs(e[i].to,x);}
}
void search(int x,int fa){reg(x){if(e[i].to==fa)continue;if(c[e[i].to]>1){ll temp=((hash[x]-size[x]*pri-1)^(hash[e[i].to]+29))+(size[x]-size[e[i].to])*pri+1;hash[e[i].to]=((hash[e[i].to]-pri*size[e[i].to]-1)^(temp+29))+size[x]*pri+1;size[e[i].to]=size[x];search(e[i].to,x);}else{ll temp=((hash[x]-size[x]*pri-1)^(hash[e[i].to]+29))+(size[x]-1)*pri+1;if(s.count(temp))ans=min(ans,e[i].to);}}
}
int main()
{n=read();rep(i,1,n-1){int u=read(),v=read();insert(u,v);}build(1,0);dfs(1,0);cnt=0;mem(last,0);rep(i,1,n){int u=read(),v=read();c[u]++,c[v]++;insert(u,v);}mem(size,0);mem(hash,0);rep(st,1,n)if(c[st]>1){build(st,0);search(st,0);break;}cout<<ans<<endl;return 0;
}

BZOJ4754 [Jsoi2016]独特的树叶

题目