有关树的同构问题。基本思想是通过树的遍历结果获得树的一种唯一表示，所以要确定子树的相对顺序。一开始想通过子树大小来确定，但同大小的子树就没法确定顺序了。而题目实际上给出了树的一种表示方法，一种基于字符串的表示方法，自然可以通过字典序确定唯一的子树相对顺序。
一开始TLE，因为在每当构造子树的唯一表示时，我都会创建一个新的字符串。参考了别人的代码后，发现可以直接用下标定位原串的子串。这里实际上也是利用了在树递归的无后效性，及对子树的修改不会影响到其他子树。进而得到一种原地修改字符串表示的算法。略有不足的是，为了排序，还是得把所有子树的字符串表示拷贝出来放到vector中。
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;void deal(string &s, int p, int q)
{if(p > q) return ;int cnt = 0, j = p;vector<string> ss;for(int i = p; i <= q; ++i){if(s[i] == '0') ++cnt;else --cnt;if(!cnt){deal(s, j + 1, i - 1);ss.push_back(s.substr(j, i - j + 1));j = i + 1;}}sort(ss.begin(), ss.end());string tmp = s.substr(0, p);for(vector<string>::iterator i = ss.begin(); i != ss.end(); ++i)tmp += *i;s = tmp + (q < s.size() - 1 ? s.substr(q + 1, s.size() - q - 1) : "");
}int main()
{
// ios::sync_with_stdio(false);string s1, s2;char t1[4000], t2[4000];int n;scanf("%d", &n);while(n--){scanf("%s %s", t1, t2);s1 = t1;s2 = t2;s1 = '0' + s1 + '1';s2 = '0' + s2 + '1';deal(s1, 0, s1.size() - 1);deal(s2, 0, s2.size() - 1);if(s1 == s2)printf("same\n");elseprintf("different\n");}return 0;
}