UOJ Logo

NOI.AC

#50. replace

统计

题目描述

如果你会一些化学知识,那你会更容易看懂这道题目。当然,本题会保证,如果你不会任何化学知识,也能看懂并且有办法做对。

从前有一棵无根树,每个节点上标注着字符 CH,所有 C 节点均恰好与其他 4 个节点相邻,而所有 H 节点恰好与其他 1 个节点相邻(即为叶子)。现在你可以将其中的一个节点上的 H 替换为 X,问一共可能有多少种本质不同的替换结果?

即使在两个不同的位置替换,所得的两棵树也有可能是同构的,所以答案并不简单等于树上 H 节点的个数。你可以通过样例来更好地理解这一点。

输入格式

从标准输入读入数据。

输入包含一个字符串,表示输入的树,从某个节点开始的深度优先搜索序列。保证这个序列以 HC 开头。

容易发现,一个合法的输入字符串会唯一确定一棵题目描述中的树,而不会引起歧义。

输出格式

输出到标准输出。

输出仅一行,包含一个正整数,表示本质不同的替换方案的个数。

样例

输入

HCHHCHHCHHH

输出

2

解释

   H  H  H
   |  |  |
H--C--C--C--H
   |  |  |
   H  H  H

可见,本质不同的替换方案只有 2 种,左侧的 3 个与右侧的 3 个 H 在替换后会得到相同的树,而中间 2 个 H 替换后会得到另一种树。

注意,如果输入改为 HCCCHHHHHHH 或者 HCHCHHHCHHH,也对应着相同的输入树,因为仅是深度优先的遍历起始点和遍历顺序发生了变化。

数据规模

10 个测试点的输入串长度依次为:14, 17, 17, 302, 302, 3002, 3002, 300002, 300002, 300002。

数据的生成方法是:初始字符串为 HCHHH,每次随机将除了开头的一个 H 替换为 CHHH