Bzoj4754 [jsoi2016]独特的树叶

树同构的好题

Posted by yjjr's blog on February 16, 2018

标签: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

5
1 2
2 3
1 4
1 5
1 2
2 3
3 4
4 5
3 6

Sample Output

1

题意

给定两棵树,分别有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;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr