ZOJ3602:Count the Trees-白红宇

ZOJ3602:Count the Trees

阅读量：5242 次

发布时间：2019-06-14

本文共 1070 字，大约阅读时间需要 3 分钟。

本来是挺容易的树同构题，可是节点数比较多，愣是把普通hash卡掉了（出题人麻烦您过来一下）

只能用map映射一下，给每个状态一个标号，而状态的表示是它两个儿子的标号。

#include#include
       
        #include
        
         #include
         
          #define MN 110001#define ll long long#define fi first#define se secondusing namespace std;int read_p,read_ca,read_f;inline int read(){    read_p=0;read_ca=getchar();read_f=1;    while(read_ca<'0'||read_ca>'9') read_f=read_ca=='-'?-1:read_f,read_ca=getchar();    while(read_ca>='0'&&read_ca<='9') read_p=read_p*10+read_ca-48,read_ca=getchar();    return read_p*read_f;}const int HA=1e6+7;int T,n,m,ha[MN],a,b,L[MN],R[MN],nm=0,mmh[2][MN];ll MMH;map
          
           
            ,int>mp;int dfs(int x,int mmh[]){ int MMH; pair
            
              now=make_pair(L[x]==-1?0:dfs(L[x],mmh),R[x]==-1?0:dfs(R[x],mmh)); if (mp.find(now)==mp.end()) MMH=mp[now]=++nm;else MMH=mp[now]; mmh[MMH]++; return MMH;}inline void work(int n,int mmh[]){ for (int i=1;i<=n;i++) L[i]=read(),R[i]=read(); dfs(1,mmh);}int main(){ T=read(); for (int i=0;i