鸡腿是CZYZ的著名DS，他为了树立高富帅的伟大形象决定暑假去张江大学学习（游玩）。张江大学自古以来就是充满了各种程序猿的地方，这里的花园自然也是十分奇葩，充满了符合程序猿口味的东西。鸡腿来到张江，自己也打理了一个小花园，小花园里种满了二叉树！
二叉树是什么呢，一棵树，除了根节点之外每个点都有父亲节点，同时每个节点只会有0个、1个或者2个孩子的树。
鸡腿在种树的过程中发现有两棵二叉树长的骨骼清奇，是树中极品。为了仔细研究这两颗树，鸡腿决定要研究一下这两棵树的共同点。鸡腿想让你帮他算一算，这两棵树上有多少相同的子树。
相同的子树指树A中的子树a和树B中的子树b完全相同，二叉树的相同定义为树上总节点个数相同，根节点孩子数相同，而且两棵子树分别相同。当然，孩子节点是有先后顺序的！
输入格式：
第一行输入两个正整数N，M表示两棵二叉树的节点个数。
第2到N+1行每行两个整数X、Y，第i+1行表示树A上节点i的左孩子和右孩子分别是谁。若没有某个孩子则用-1表示。
第N+2到N+M+1行每行两个正整数X、Y，第i+N+1行表示树B上节点i的左孩子和右孩子分别是谁。若没有某个孩子同样用-1表示。
输出格式：
一行输出一个整数ANS表示相同子树的个数。
样例输入：
Case 1:
2 2
-1 2
-1 -1
2 -1
-1 -1
Case 2:
5 5
2 3
4 5
-1 -1
-1 -1
-1 -1
2 3
4 5
-1 -1
-1 -1
-1 -1
样例输出：
Case 1:
1
Case 2:
11
数据范围：
对于20%的数据1 ≤ N，M ≤ 100；
对于40%的数据1≤N，M ≤5,000；
对于100%的数据1≤ N，M ≤ 100,000。
时间限制：
1s
空间限制：
256M
提示：
样例1如下图：
< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPGJyPgogPGJyPgo8cD48YnI+CjwvcD4KPHA+0vLOqszixL/Jz7j4wcvV4r/Dyve63Lbgz97WxqOsysfN6sirz+C1yLLFxNy21LTwsLi5sc/XvNPSu6Osy/nS1M/rtb1oYXNooaM8L3A+CjxwPr7fzOXAtMu1vs3Kx7m51OzSu7j2uf7Po7qvyv3AtLHtyr7Su7/Dtv6y5sr3o6yyu8rHzKvE0aGjPC9wPgo8cD61q9XitcDM4rj4ztLX7rTzuNC0pcrHaGFzaLqvyv21xNGhyKHM2LHw1tjSqqOs0qqz5LfWv7zCx7K7u+HW2Li0o6y78tXf1ti4tLXEvqHBv8nZo6zIu7rzv8nS1MrKtbHTw7bguPZoYXNouq/K/aGjPC9wPgo8cD48YnI+CjwvcD4KPHA+PHByZSBjbGFzcz0="brush:java;">#include
#include
#include
#include
#include
#include
#include
#include
using namespace std; int N,M; int lc[1200000],rc[1200000]; long long hash[30][30]; long long key[30][120000]; long long size[5][10000007]; const long long mod=10000007; void DFS(int x){ if (lc[x]>0) DFS(lc[x]); if (rc[x]>0) DFS(rc[x]); long long L[5],R[5]; if (lc[x]==-1) L[0]=L[1]=L[2]=0;else {L[0]=key[0][lc[x]];L[1]=key[1][lc[x]];L[2]=key[2][lc[x]];} if (rc[x]==-1) R[0]=R[1]=R[2]=0;else {R[0]=key[0][rc[x]];R[1]=key[1][rc[x]];R[2]=key[2][rc[x]];} key[0][x]=(hash[0][0]*L[0]+hash[0][1]*R[0]*R[0]+hash[0][2]*(L[0]^R[0])+hash[0][3])%mod; key[1][x]=(hash[1][0]*L[1]+hash[1][1]*R[1]*R[1]+hash[1][2]*(L[1]^R[1])+hash[1][3])%mod; key[2][x]=(hash[2][0]*L[2]+hash[2][1]*R[2]*R[2]+hash[2][2]*(L[2]^R[2])+hash[2][3])%mod; size[0][key[0][x]]++; size[1][key[1][x]]++; size[2][key[2][x]]++; } long long Ans=0; void work(int x){ if (lc[x]>0) work(lc[x]); if (rc[x]>0) work(rc[x]); long long L[5],R[5]; if (lc[x]==-1) L[0]=L[1]=L[2]=0;else {L[0]=key[0][lc[x]];L[1]=key[1][lc[x]];L[2]=key[2][lc[x]];} if (rc[x]==-1) R[0]=R[1]=R[2]=0;else {R[0]=key[0][rc[x]];R[1]=key[1][rc[x]];R[2]=key[2][rc[x]];} key[0][x]=(hash[0][0]*L[0]+hash[0][1]*R[0]*R[0]+hash[0][2]*(L[0]^R[0])+hash[0][3])%mod; key[1][x]=(hash[1][0]*L[1]+hash[1][1]*R[1]*R[1]+hash[1][2]*(L[1]^R[1])+hash[1][3])%mod; key[2][x]=(hash[2][0]*L[2]+hash[2][1]*R[2]*R[2]+hash[2][2]*(L[2]^R[2])+hash[2][3])%mod; long long Min=10000000000000ll; Min=min(Min,size[0][key[0][x]]); Min=min(Min,size[1][key[1][x]]); Min=min(Min,size[2][key[2][x]]); Ans+=Min; } int vis[112000],root; int main(){ // freopen("a.in","r",stdin); // freopen("a.out","w",stdout); hash[0][0]=223;hash[0][1]=293;hash[0][2]=311;hash[0][3]=251; hash[1][0]=349;hash[1][1]=353;hash[1][2]=357;hash[1][3]=373; hash[2][0]=577;hash[2][1]=593;hash[2][2]=599;hash[2][3]=379; scanf("%d%d",&N,&M); for (int i=1;i<=N;i++){ scanf("%d%d",&lc[i],&rc[i]); if (lc[i]>0) vis[lc[i]]=1; if (rc[i]>0) vis[rc[i]]=1; } for (int i=1;i<=N;i++) if (!vis[i]) {root=i;break;} DFS(root); memset(vis,0,sizeof(vis)); memset(lc,0,sizeof(lc)); memset(rc,0,sizeof(rc)); memset(key,0,sizeof(key)); for (int i=1;i<=M;i++){ scanf("%d%d",&lc[i],&rc[i]); if (lc[i]>0) vis[lc[i]]=1; if (rc[i]>0) vis[rc[i]]=1; } for (int i=1;i<=M;i++) if (!vis[i]) {root=i;break;} work(root); printf("%lld\n",Ans); return 0; }