zoj 3602

给你两颗二叉树，左右子树不可旋转，求这两个棵树相同的子树的个数。可以给每一种子树的形态一个编号，那么我们只要统计第一个颗树中每种形态的子树有多少个，然后把第二颗树中相同子树的数目与之相乘就可以了。我们可以设定叶子节点的形态编号为0，用一个map来存放hash值，而任何一个节点的哈希值都可用左右子树的形态编号形成的pair唯一表示。

View Code

  1 // File Name: 3602.cpp
  2 // Author: Missa
  3 // Created Time: 2013/2/5 星期二 11:47:26
  4 
  5 #include<iostream>
  6 #include<cstdio>
  7 #include<cstring>
  8 #include<algorithm>
  9 #include<cmath>
 10 #include<queue>
 11 #include<stack>
 12 #include<string>
 13 #include<vector>
 14 #include<cstdlib>
 15 #include<map>
 16 using namespace std;
 17 const int maxn = 1e5+5;
 18 struct node
 19 {
 20     int l,r;
 21     node(){}
 22     node(int l,int r):l(l),r(r){}
 23 }t1[maxn],t2[maxn];
 24 int n,m;
 25 bool operator <(const node&a,const node &b)
 26 {
 27     if(a.l==b.l) return a.r<b.r;
 28     return a.l<b.l;
 29 }
 30 int ord[maxn];//bfs一次形成的顺序
 31 int o_num;
 32 map<node,int>ha,cnt;//ha用来判断同构,cnt用来计数
 33 int st[maxn];//节点的形态
 34 void build()
 35 {
 36     queue<int>q;
 37     while(!q.empty()) q.pop();
 38     ha.clear();
 39     cnt.clear();
 40     q.push(1);
 41     o_num=0;
 42     while(!q.empty())
 43     {
 44         int cur=q.front();q.pop();
 45         ord[o_num++]=cur;
 46         if(t1[cur].l>0) q.push(t1[cur].l);
 47         if(t1[cur].r>0) q.push(t1[cur].r);
 48     }
 49     int type=0;
 50     memset(st,0,sizeof(st));
 51     for(int i=n-1;i>=0;i--)
 52     {
 53         int tmp=ord[i];
 54         int ll=t1[tmp].l>0?st[t1[tmp].l]:0;
 55         int rr=t1[tmp].r>0?st[t1[tmp].r]:0;
 56         node p=node(ll,rr);
 57         if(ha.find(p)==ha.end())
 58             ha[p]=++type;
 59         st[ord[i]]=ha[p];
 60         cnt[p]++;
 61     }
 62     //cout<<"mark\n";
 63 }
 64 void gao()
 65 {
 66     queue<int>q;
 67     while(!q.empty()) q.pop();
 68     q.push(1);
 69     o_num=0;
 70     while(!q.empty())
 71     {
 72         int cur=q.front();q.pop();
 73         ord[o_num++]=cur;
 74         if(t2[cur].l>0) q.push(t2[cur].l);
 75         if(t2[cur].r>0) q.push(t2[cur].r);
 76     }
 77     memset(st,0,sizeof(st));
 78     long long ans=0;
 79     for(int i=m-1;i>=0;i--)
 80     {
 81         int tmp=ord[i];
 82         int ll=t2[tmp].l>0?st[t2[tmp].l]:0;
 83         int rr=t2[tmp].r>0?st[t2[tmp].r]:0;
 84         node p=node(ll,rr);
 85         if(ha.find(p)==ha.end())
 86         {
 87             st[tmp]=-1;
 88             continue;
 89         }
 90         ans+=cnt[p];
 91         st[tmp]=ha[p];
 92     }
 93     printf("%lld\n",ans);
 94 }
 95 
 96 int main()
 97 {
 98     int test;
 99     scanf("%d",&test);
100     while(test--)
101     {
102         scanf("%d%d",&n,&m);
103         memset(t1,-1,sizeof(t1));
104         memset(t2,-1,sizeof(t2));
105         for(int i=1;i<=n;i++)
106             scanf("%d%d",&t1[i].l,&t1[i].r);
107         for(int i=1;i<=m;i++)
108             scanf("%d%d",&t2[i].l,&t2[i].r);
109         //cout<<"r\n";
110         build();
111         gao();
112     }
113     return 0;
114 }