POJ1635 Subway Tree Systems

题意

用一串 $0/1$ 序列表示一棵树的 $\text{dfs}$ 路径，$0$ 表示远离根节点，$1$ 表示靠近根节点。给出两个序列，判断它们是不是同构的树。

序列长度 $L\le 3000$ 。

题解

对每棵树做 $\text{dfs}$ ，回溯时根据与当前节点相连子树的 $\text{hash}$ 值算出当前子树的 $\text{hash}$ 值，最后比较根节点的 $\text{hash}$ 值即可。

记录 $0$ 的个数 $S_0$ 和 $1$ 的个数 $S_1$ ，如果 $S_0=S_1$ 就表示已经访问过了一棵子树，然后递归求解这个子树即可。

注意访问顺序不同也可能同构，所以应该对子树的 $\text{hash}$ 值进行排序后再计算。

#include<bits/stdc++.h>
#define ha 19260817
#define ull unsigned long long

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

char s[3005];

ull get_hash(int l,int r)
{
    int cnt=0,s0=0,s1=0,st=l,v[(r-l+1)/2+1];
    for (int i=l;i<=r;i++)
    {
        s1+=s[i]=='1';
        s0+=s[i]=='0';
        if (s0!=s1) continue;
        v[++cnt]=get_hash(st+1,i-1);
        st=i+1;
    }
    sort(v+1,v+cnt+1);
    ull ans=1;
    for (int i=1;i<=cnt;i++) ans=ans*ha+v[i];
    return ans;

}

signed main()
{
    int n=read();
    while (n--)
    {
        scanf("%s",s);
        ull a=get_hash(0,strlen(s)-1);
        scanf("%s",s);
        if (get_hash(0,strlen(s)-1)==a) puts("same");
        else puts("different");
    }
    return 0;
}