【LOJ#6066】「2017 山东一轮集训 Day3」第二题（哈希，二分）

题面

题解

要哈希是很显然的，那么就考虑哈希什么。。。

要找一个东西可以表示一棵树，所以我们找到了括号序列。

那么二分一个答案\(d\)，把所有点挂到\(d+1\)次祖先上去，那么\(d+1\)次祖先的哈希值就是它原本的括号序列挖去了若干段，直接暴力哈希拼接起来就好了。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<set>

using namespace std;

#define MAX 100100

#define ull unsigned long long

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

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

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

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

	return t?-x:x;

}

int n;

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

int h[MAX],cnt=1;

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

int p[20][MAX],lg[MAX],dfn[MAX],low[MAX],dep[MAX];

int a[MAX<<1],tot,maxdep;

ull pw[MAX<<1],H[MAX<<1];

const ull base=233;

void dfs(int u,int ff)

{

	p[0][u]=ff;a[++tot]=1;dfn[u]=tot;dep[u]=dep[ff]+1;

	for(int j=1;j<=lg[n];++j)p[j][u]=p[j-1][p[j-1][u]];

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

	a[++tot]=0;low[u]=tot;

}

int parent(int x,int k)

{

	for(int i=lg[n];~i;--i)

		if(k&(1<<i))x=p[i][x];

	return x;

}

ull hs(int l,int r){return H[r]-H[l-1]*pw[r-l+1];}

vector<int> son[MAX];

bool cmp(int a,int b){return dfn[a]<dfn[b];}

set<ull> S;

bool vis[MAX];

bool check(int d)

{

	for(int i=0;i<=n;++i)vis[i]=false,son[i].clear();

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

	{

		int ff=parent(i,d);vis[ff]=true;

		son[p[0][ff]].push_back(i);

	}

	S.clear();

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

	{

		int l=son[i].size();if(!vis[i])continue;

		sort(son[i].begin(),son[i].end(),cmp);

		int L=dfn[i];ull H=0;

		for(int j=0;j<l;++j)

			H=H*pw[dfn[son[i][j]]-L]+hs(L,dfn[son[i][j]]-1),L=low[son[i][j]]+1;

		H=H*pw[low[i]-L+1]+hs(L,low[i]);

		if(S.find(H)!=S.end())return true;

		S.insert(H);

	}

	return false;

}

int main()

{

	n=read();pw[0]=1;

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

	{

		int x=read();

		for(int j=1;j<=x;++j)Add(i,read());

	}

	for(int i=2;i<=n;++i)lg[i]=lg[i>>1]+1;

	for(int i=1;i<=n+n;++i)pw[i]=pw[i-1]*base;

	dfs(1,0);

	for(int i=1;i<=tot;++i)H[i]=H[i-1]*base+a[i];

	for(int i=1;i<=n;++i)maxdep=max(maxdep,dep[i]);

	int l=1,r=maxdep,ret=0;

	while(l<=r)

	{

		int mid=(l+r)>>1;

		if(check(mid))l=mid+1,ret=mid;

		else r=mid-1;

	}

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

	return 0;

}