bLue的二叉树

Time Limit: 3000 ms Memory Limit: 65536 KiB

Problem Description

Keke 是一个喜爱种树的人,他对各种树都有很深的研究。

MLE 听说 bLue 种了一些新品种的树,就想邀请 Keke 去围观一下。

PBH 在暗中把这一切尽收眼底,作为资深植树行家,他虽不屑,但也决定和他们一起去看一看。

于是,大家便一起到了 bLue 家去看树。

bLue 有两棵二叉树,分别有 n 和 m 个节点,编号分别为 1-n 和 1-m,每个节点都有一个权值,bLue 想知道第一棵树的所有子树中与第二棵树完全相同的个数(不考虑节点编号)。

Input

输入数据有多组(数据组数不超过 150),到 EOF 结束。

对于每组数据:

  • 第一行有两个整数 n (0 < n <= 10^5) 和 m (0 < m <= 10^5),表示第一棵树和第二棵树的节点个数
  • 接下来 n 行,表示第一棵树:第 i (0 < i <= n) 行有 3 个整数,w[i] (0 < w[i] <= 10), lc[i], rc[i] (0 < lc[i], rc[i] <= n),分别表示节点 i 的权值,该节点的左孩子编号和右孩子编号,若某个孩子不存在,则为 0 (数据保证每棵树都是合法的有根二叉树)
  • 接下来 m 行,表示第二棵树:格式同第一棵树

保证:树的最大深度不会超过 10000。

Output

对于每组数据,输出一行一个整数 num,表示第一棵树的所有子树中与第二棵树完全相同的个数。

Sample Input

7 4
1 6 3
2 0 4
1 7 0
3 0 0
1 2 1
2 0 0
2 0 0
2 0 0
1 4 0
1 1 2
2 0 0
3 3
1 0 0
2 1 3
3 0 0
1 0 3
2 1 0
3 0 0

Sample Output

1
0

Hint

数据量比较大,推荐用 scanf 等读入。

Source

【“师创杯”山东理工大学第九届ACM程序设计竞赛 正式赛】不得不放弃、