题解：地铁系统树结构判断

这段代码解决的是一个关于判断两个二进制字符串是否表示同一棵树的DFS遍历序列的问题。问题描述中，地铁系统被建模为一棵树，从中央车站出发进行深度优先遍历（DFS），用0表示向远离中央车站的方向移动，用1表示向中央车站返回的方向移动。代码需要判断两个这样的遍历序列是否对应同一棵树结构。

问题分析

给定两个由0和1组成的字符串，每个字符串代表一个有效的树的DFS遍历序列。需要判断这两个序列是否对应同一棵树结构。关键在于理解树的结构可以通过遍历序列中的父子关系来确定，而不需要考虑具体的遍历顺序。

代码思路

1. 解析遍历序列：从每个字符串构建树的父子关系。
2. 计算子树大小：对于每个节点，计算其所有子节点的数量（包括自身）。
3. 比较子树大小分布：如果两个树的所有节点的子树大小分布相同，则认为它们是同一棵树。

代码详细解释

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int t,len[2],a[30001],b[30001],fa[2][30001],num[2][30001];
bool flag;
char s[2][30001];

// 解析遍历序列，构建父子关系
void findd(int u)
{
    int now=-1;  // 当前父节点的索引
    for(int i=1;i<=len[u];i++)
        if(s[u][i]=='0')  // 遇到0表示向下移动到子节点
        {
            fa[u][i]=now;  // 当前节点的父节点是now
            now=i;         // 更新当前节点为i
        }
        else now=fa[u][now];  // 遇到1表示向上返回，更新当前节点为其父节点
}

// 计算每个节点的子树大小
void cal(int u)
{
    int now=-1;  // 当前节点的索引
    for(int i=1;i<=len[0];i++)
        if(s[u][i]='1')  // 遇到1表示返回父节点，此时可以计算子树大小
        {
            now=i;
            while(now!=-1)  // 向上更新所有祖先节点的子树大小
            {
                num[u][now]++;  // 子树大小加1
                now=fa[u][now];  // 继续更新父节点
            }
        }
}

int main()
{
    scanf("%d",&t);  // 读取测试用例数量
    while(t--)
    {
        scanf("%s%s",s[0]+1,s[1]+1);  // 读取两个遍历序列
        flag=0;  // 标记是否发现不同
        len[0]=strlen(s[0]+1);  // 计算字符串长度
        len[1]=strlen(s[1]+1);
        
        if(len[0]!=len[1])  // 如果长度不同，直接判定为不同
        {
            puts("different");
            continue;
        }
        
        // 初始化父子关系和子树大小数组
        memset(fa[0],-1,sizeof(fa[0]));
        memset(fa[1],-1,sizeof(fa[1]));
        memset(num[0],0,sizeof(num[0]));
        memset(num[1],0,sizeof(num[1]));
        
        // 解析遍历序列，计算子树大小
        findd(0);
        cal(0);
        findd(1);
        cal(1);
        
        // 排序子树大小数组
        sort(num[0]+1,num[0]+len[0]+1);
        sort(num[1]+1,num[1]+len[1]+1);
        
        // 比较排序后的子树大小数组
        for(int i=1;i<=len[0];i++)
            if(num[0][i]!=num[1][i])
            {
                puts("different");
                flag=1;
                break;
            }
        
        if(!flag) puts("same");  // 如果所有子树大小都相同，则判定为相同
    }
    return 0;
}

复杂度分析

• 时间复杂度：O(T * N log N)，其中T是测试用例数量，N是字符串长度。每个测试用例需要O(N)时间构建父子关系和计算子树大小，以及O(N log N)时间进行排序。
• 空间复杂度：O(N)，主要用于存储父子关系和子树大小数组。

这个算法通过分析树的结构特征（子树大小分布）来判断两个遍历序列是否对应同一棵树，巧妙地避开了直接比较遍历顺序的复杂性。