题目链接

解题思路

??求出两个字符串代表的树的最小表示，进行比对就能得到答案，为了方便处理，给他设定一个根，即在开头加一个0，当然在结尾也要再加上一个0。
??关于最小表示的求法，每次都求出子树字典序最小的组合方式，然后向上合并为字典序最小的组合方式即可，显然可以用递归来完成。

代码

const int maxn = 1e5+10;int u,p[maxn];string dfs(string s) { ++u; vector<string> tmp; while(s[u]==‘0‘) tmp.push_back(dfs(s)); ++u; sort(tmp.begin(),tmp.end()); string res = "0"; for (auto s : tmp) res += s; res += ‘1‘; return res;}int main(){ int t; cin >> t; while(t--) { string s1,s2; cin >> s1 >> s2; s1 = ‘0‘+s1+‘1‘; s2 = ‘0‘+s2+‘1‘; u = 0; string rs1 = dfs(s1); u = 0; string rs2 = dfs(s2); if (rs1==rs2) puts("same"); else puts("different"); } return 0;}