Keke 是一个喜爱种树的人，他对各种树都有很深的研究。
MLE 听说 bLue 种了一些新品种的树，就想邀请 Keke 去围观一下。
PBH 在暗中把这一切尽收眼底，作为资深植树行家，他虽不屑，但也决定和他们一起去看一看。
于是，大家便一起到了 bLue 家去看树。
bLue 有两棵二叉树，分别有 n 和 m 个节点，编号分别为 1-n 和 1-m，每个节点都有一个权值，bLue 想知道第一棵树的所有子树中与第二棵树完全相同的个数(不考虑节点编号)。
输入数据有多组（数据组数不超过 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。
对于每组数据，输出一行一个整数 num，表示第一棵树的所有子树中与第二棵树完全相同的个数。
数据量比较大，推荐用 scanf 等读入。
官方题解：
[3926] E - bLue的二叉树 by 不得不放弃、 这个题题意很简单，就是求 A 树中的 n 个非空子树中与 B 树相同的个数。 直接暴力求解当然是会 TLE 的，不过加上一些剪枝应该是可以过的。 比如先一遍 DFS 把 A 树的每个子树的深度求解出来，再依次与 B 树对比，如果当前子树的深度与 B 树的深度相同并且当前节点的权值与 B 树的根节点的权值相等，那么就再 DFS 验证一下。 本题还可以哈希过，对每个子树进行哈希，再对比即可，不过哈希的姿势要好。 那么最简单的解法是什么呢？ 这个题是用 KMP 做的（其实题目前三行也有暗示 2333）。 先分别把两棵树的权值的前序或者后序遍历序列（以下简称序列）跑出来，注意空节点用一个题目 里不存在的权值表示，然后 A 串作为母串，B 串作为子串，直接求 A 中 B 出现的次数即可。 容易知道，两颗相同的树的序列是完全相等的，我们把它扩展一下，到一棵树的某个子树与另一棵 树比较，作为一颗子树，它的序列必定是整棵树的序列的字串（注意不是子序列），这样的话就很 容易想到用 KMP（也可以用其他匹配算法）来做。 那么有人就有疑问了，如果两个不同子树的序列连起来刚好包含了 B 树的序列怎么办？ 前面提到过，空节点也要放进序列里面，并且要用题目里不会出现的权值，这样就可以避免这个问 题。
#include<bits/stdc++.h> #define LL long long #define MEM(a, b) memset(a, b, sizeof(a)) using namespace std; struct Node { int w, lc, rc; }; Node a[100005], b[100005]; int avis[100005], bvis[100005]; int na[100005 * 3 + 10], nb[100005 * 3 + 10]; // 包含空节点所以数组大小扩大3倍 int nest[100005 * 3 + 10]; int la, lb; void adfs(int x) { na[la++] = a[x].w; if(x == 0) return; adfs(a[x].lc); adfs(a[x].rc); } void bdfs(int x) { nb[lb++] = b[x].w; if(x == 0) return; bdfs(b[x].lc); bdfs(b[x].rc); } void Getnest(int n) { int j = 0; int i = 1; nest[1] = 0; while(i <= n) { if(j == 0 || nb[i] == nb[j]) { j++; i++; if(nb[i] == nb[j]) nest[i] = nest[j]; else nest[i] = j; } else j = nest[j]; } } int kmp(int n, int m) { int i = 1; int j = 1; int ans = 0; while(i <= n) { if(j == 0 || na[i] == nb[j]) { i++; j++; } else j = nest[j]; if(j >= m + 1) { ans++; j = nest[j]; } } return ans; } int main() { int n, m; while(scanf("%d %d", &n, &m) != EOF) { MEM(avis, 0); MEM(bvis, 0); for(int i = 1 ; i <= n ; i++) { scanf("%d %d %d", &a[i].w, &a[i].lc, &a[i].rc); avis[a[i].lc]++; avis[a[i].rc]++; } for(int i = 1 ; i <= m ; i++) { scanf("%d %d %d", &b[i].w, &b[i].lc, &b[i].rc); bvis[b[i].lc]++; bvis[b[i].rc]++; } la = lb = 1; for(int i = 1 ; i <= n ; i++) if(avis[i] == 0) { adfs(i); break; } for(int i = 1 ; i <= m ; i++) if(bvis[i] == 0) { bdfs(i); break; } Getnest(lb - 1); int ans = kmp(la - 1, lb - 1); printf("%d\n", ans); } }
