Description

给一棵\(n\)个节点的有根树，定义两棵树同构当且仅当他们每个深度的节点个数相同。问这个树上有多少对子树满足同构。\(n\le100000\)。

sol

树\(hash\)。

每个深度的节点个数，类似于一个多项式？所以定义\(hash\)函数:

\[Hash(u)=base1+base2\sum Hash(v)
\]

最后判相等就不说了，\(sort\)一遍再搞一搞就好了。

code

在我交换\(base1\)和\(base2\)的值之前它是\(WA\)的。。。

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

int gi(){

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

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

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

#define ull unsigned long long

const int N = 2e5+5;

const ull base2 = 20020415;

const ull base1 = 20011118;

int n,to[N],nxt[N],head[N],cnt;

ull Hash[N],ans;

void link(int u,int v){

	to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;

}

void dfs(int u,int f){

	Hash[u]=base1;

	for (int e=head[u];e;e=nxt[e])

		if (to[e]!=f) dfs(to[e],u),Hash[u]+=Hash[to[e]]*base2;

}

int main(){

	n=gi();

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

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

		link(u,v);link(v,u);

	}

	dfs(1,0);sort(Hash+1,Hash+n+1);

	for (int i=1,j;i<=n;i=j){

		j=i+1;

		while (j<=n&&Hash[j]==Hash[i]) ++j;

		ans+=1ll*(j-i)*(j-i-1)/2;

	}

	printf("%llu\n",ans);return 0;

}

巴特西

[Aizu2784]Similarity of Subtrees

Description

sol

code

最新文章

热门文章