【BZOJ4754】独特的树叶（哈希）

题面

BZOJ

给定一个\(n\)个节点的树A和一个\(n+1\)个节点的树\(B\)

求\(B\)的一个编号最小的节点，使得删去这个节点后\(A,B\)同构

题解

树哈希

一个奇怪的姿势

总而言之，就是把树的各种信息乱七八糟的拼在一起强行哈希一下

真搞不懂这种丧病的东西为什么还能直接出成省选题，

随便一个模数还可能\(WA\)。。。

这种东西依我看只适合\(IOI\)赛制

至于怎么搞？想怎么搞怎么搞啊。。。。

你可以把子树的哈希值排序再哈希

也可以直接异或起来（这个很不错）

甚至还可以像菊开那样直接跑快速幂

反正想怎么玩怎么玩。。。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 111111

#define ull unsigned long long

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

struct Line{int v,next;}e[MAX<<1];

int h[MAX],cnt,size[MAX],n;

void Add(int u,int v){e[++cnt]=(Line){v,h[u]};h[u]=cnt;}

ull hash[MAX];

set<ull> M;

const ull base1=1702;

const ull base3=998244353;

const ull base2=1000000007;

int ans=1e9;

int deg[MAX];

void dfs(int u,int ff)

{

	hash[u]=0;size[u]=1;

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;if(v==ff)continue;

		dfs(v,u);size[u]+=size[v];

		hash[u]^=hash[v]+base1;

	}

	hash[u]+=base2*size[u]+base3;

}

void Calc(int u,int ff)

{

	M.insert(hash[u]);

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;if(v==ff)continue;

		ull tmp=((hash[u]-base2*n-base3)^(hash[v]+base1))+base2*(n-size[v])+base3;

		hash[v]=((hash[v]-base2*size[v]-base3)^(tmp+base1))+base2*n+base3;

		Calc(v,u);

	}

}

void Calc2(int u,int ff)

{

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;if(v==ff)continue;

		if(deg[v]>1)

		{

			ull tmp=((hash[u]-base2*n-base3)^(hash[v]+base1))+base2*(n-size[v])+base3;

			hash[v]=((hash[v]-base2*size[v]-base3)^(tmp+base1))+base2*n+base3;

			Calc2(v,u);

		}

		else

		{

			ull tmp=((hash[u]-base2*n-base3)^(hash[v]+base1))+base2*(n-1)+base3;

			if(M.count(tmp))

				ans=min(ans,v);

		}

	}

}

int main()

{

	n=read();

	for(int i=1;i<n;++i)

	{

		int u=read(),v=read();

		Add(u,v);Add(v,u);

	}

	dfs(1,0);Calc(1,0);

	memset(h,0,sizeof(h));cnt=0;

	for(int i=1;i<=n;++i)

	{

		int u=read(),v=read();

		Add(u,v);Add(v,u);

		++deg[u];++deg[v];

	}

	for(int i=1;i<=n;++i)

		if(deg[i]>1)

		{

			++n;dfs(i,0);Calc2(i,0);

			break;

		}

	printf("%d\n",ans);

	return 0;

}

巴特西

【BZOJ4754】独特的树叶（哈希）

【BZOJ4754】独特的树叶（哈希）

题面

题解

最新文章

热门文章