题目描述

一些主要城市拥有树形的地铁系统，即在任何一对车站之间，有且只有一种方式可以乘坐地铁。

此外，这些城市大多数都有一个中央车站。

想象一下，你是一名在拥有树形地铁系统的城市游玩的游客，你想探索该城市完整的地铁线路。

你从中央车站出发，随机选择一条地铁线，然后乘坐地铁行进。

每次到达一个车站，你都将选择一条尚未乘坐过的地铁线路进行乘坐。

如果不存在未乘坐过的线路，则退回到上一个车站，再做选择。

直到你将所有地铁线路都乘坐过两次（往返各一次），此时你将回到中央车站。

之后，你以一种特殊的方式回忆自己的坐车过程，你将你的完整地铁乘坐路线编码为一个二进制字符串。

其中0编码表示你乘坐地铁线路到达距离中央车站更远的一站，1编码表示你乘坐地铁线路到达距离中央车站更近的一站。

样例

输入
2
0010011101001011
0100011011001011
0100101100100111
0011000111010101

输出
same
different

算法1

(树的最小表示) $O(n^2)$

先解释一下题意，有n组数据，每个数据给两个树的dfs序，0表示向下走，1表示向上走，问这两个树是不是同构的。

如何判断两个树是不是同构：求出每个树的最小表示。即与这棵树同构的最小的dfs序。如果两个树同构，那么这两个树的最小表示 应该相同。 求树的最小表示可以递归实现，求出所有子树的dfs序，然后从小到大排序拼接起来

C++ 代码

#include <iostream>
#include <algorithm>
#include<cstdio>
#include <vector>
using namespace std;
string dfs(string &s,int &u){
    u++;
    vector<string> v;
    while(s[u]=='0') v.push_back(dfs(s,u));
    u++;
    sort(v.begin(),v.end());
    string ans="0";
    for(string &ss:v) ans+=ss;
    ans+='1';
    return ans;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        string a,b;
        cin>>a>>b;
        a='0'+a+'1';
        b='0'+b+'1';
        int ua=0,ub=0;
        string ra=dfs(a,ua),rb=dfs(b,ub);
        if(ra==rb) printf("same\n");
        else printf("different\n");
    }
    return 0;
}