P5043【模板】树同构（[BJOI2015]树的同构）

思路：树哈希

提交：1次

题解：

怕不是用的oi-wiki上的公式：

\[f_u=size_u\times\sum f_{son_{u,i}}\times Base^{i-1}
\]

#include<bits/stdc++.h>

#define R register int

using namespace std;

namespace Luitaryi {

template<class I> inline I g(I& x) { x=0; register I f=1;

	register char ch; while(!isdigit(ch=getchar())) f=ch=='-'?-1:f;

	do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x*=f;

}

#define u32 unsigned int

const int N=60,Inf=1e+9;

const u32 B=23333u;

int T,n[N],cnt,sum;

int vr[N<<1],nxt[N<<1],fir[N];

inline void add(int u,int v) {

	vr[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt;

	vr[++cnt]=u,nxt[cnt]=fir[v],fir[v]=cnt;

}

int sz[N],mx[N];

u32 hsh[N],buf[N],vl[N][2];

inline void calc(int u,int fa) {

	sz[u]=1; for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];

		if(v==fa) continue; calc(v,u),sz[u]+=sz[v];

	} R size=0;

	for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];

		if(v==fa) continue; buf[++size]=hsh[v];

	} sort(buf+1,buf+size+1);

	u32 vl=0; for(R i=1;i<=size;++i) vl=vl*B+buf[i];

	hsh[u]=vl?vl*sz[u]:1;

}

inline void getsz(int u,int fa) {

	sz[u]=1,mx[u]=0;

	for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];

		if(v==fa) continue; getsz(v,u); sz[u]+=sz[v];

		mx[u]=max(mx[u],sz[v]);

	} mx[u]=max(mx[u],sum-sz[u]);

}

inline void main() {

	g(T); for(R i=1;i<=T;++i) {

		sum=g(n[i]); for(R u=1,v;u<=n[i];++u) g(v),v?add(u,v):(void)0;

		getsz(1,0); R sz=Inf,tot=0;

		for(R u=1;u<=n[i];++u) sz=min(sz,mx[u]);

		for(R u=1;u<=n[i];++u) if(mx[u]==sz) calc(u,0),vl[i][tot]=hsh[u],++tot;

		if(tot==2&&vl[i][0]>vl[i][1]) swap(vl[i][0],vl[i][1]);

		cnt=0,memset(fir,0,sizeof(fir)),memset(nxt,0,sizeof(nxt)),memset(hsh,0,sizeof(hsh));

	}

	for(R i=1;i<=T;++i) { register bool flg=true;

		for(R j=1;j<i;++j) if(n[i]==n[j]&&vl[i][0]==vl[j][0]&&vl[i][1]==vl[j][1]) {

			flg=false; printf("%d\n",j); break;

		} if(flg) printf("%d\n",i);

	}

}

} signed main() {Luitaryi::main(); return 0;}

2019.09.03

66

巴特西

P5043【模板】树同构（[BJOI2015]树的同构）

思路：树哈希

提交：1次

题解：

最新文章

热门文章