[AIZU2784]Similarity of Subtrees(树Hash)

发布于 2018-05-24  107 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[AIZU2784]Similarity of Subtrees(树Hash)

Description

Define the depth of a node in a rooted tree by applying the following rules recursively:

Let S(T,d) be the number of nodes of T with depth d. Two rooted trees T and T′ are similar if and only if S(T,d) equals S(T′,d) for all non-negative integer d
You are given a rooted tree Twith N nodes. The nodes of T are numbered from 1 to N. Node 1 is the root node of T. Let Ti be the rooted subtree of T whose root is node i. Your task is to write a program which calculates the number of pairs (i,j) such that Ti and Tj are similar and i<j.

Tag

树Hash

题目大意

给出一棵有根树,定义两棵树是同构的当且仅当每一层的节点数都相同,求同构的子树对数。

解决思路

根据题目对同构的树的定义,可以得到合适树$$Hash$$的函数,即对于$$u$$的儿子$$v$$,有
\[Hash[u]=\sum Hash[v]*base\]
求完$$hash$$之后,排一边序,找出相同的,统计答案。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[AIZU2784]Similarity of Subtrees(树Hash)


HNCJ OIer