Subway tree systems
题目大意:给出两串含有‘1’和‘0’的字符串，0表示向下搜索，1表示回溯，这样深搜一颗树，深搜完之后问这两棵树是不是同一棵树
/*
在poj上交需要加一个string头文件，不然会CE
树的最小表示
这里用的最小表示法就是将树的所有子树分别用1个字符串表示，要按字典序排序将他们依依连接起来。连接后如果两个字符串是一模一样的，那么他们必然是同构的。这样原问题就变成了子问题，子树又是一颗新的树。
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
string s1,s2;
string mn(string str){//得到树的最小表示
int dep=,st=;
vector<string>a;
string stemp;
for(int i=;i<str.size();i++){
dep+=str[i]==''?-:;
if(!dep){
stemp=""+mn(str.substr(st+,i-st))+"";
a.push_back(stemp);
st=i+;
}
}
sort(a.begin(),a.end());
stemp=string("");
for(int i=;i<a.size();i++)stemp+=a[i];
return stemp;
}
int main(){
freopen("Cola.txt","r",stdin);
int T;scanf("%d",&T);
while(T--){
cin>>s1>>s2;
string ss1=mn(s1);
string ss2=mn(s2);
if(ss1==ss2)puts("same");
else puts("different");
}
}