POJ 1635 Subway tree systems(进阶指南，树的最小表示，递归)

算法竞赛进阶指南，91 页，树的最小表示

本题要点：
1、树的最小表示 ，用 01 字符串来表示一个树（每个节点可以有任意多个孩子节点），
从树的根节点开始遍历每条边， 每条边走两次， 每走一次边，写上 0 或 1， 所有字符串连起来就是一个树的01表示
从父节点走向子节点，用 '0’表示;
从子节点走向父节点，用 '1’表示;
假如某个子树的根节点是 father， 其所有的子节点为 son[1], son[2], …, son[n]，遍历过程如下：
father走向 son[1] （'0’表示）, 遍历son[1] 的所有孩子节点（产生一段01字符串），从 son[1] 走向 father （'1’表示），
father走向 son[2] （'0’表示）, 遍历son[2] 的所有孩子节点（产生一段01字符串），从 son[2] 走向 father （'1’表示），
…
father走向 son[n] （'0’表示）, 遍历son[n] 的所有孩子节点（产生一段01字符串），从 son[n] 走向 father （'1’表示），
所有的 01 串起来，得到 以 father 为 根的子树的一个 01 表示。然而，father 访问孩子的顺序是可以任意改变的，然后就得到若干个 01字符串，
其中字典序最小的是 树的最小表示
2、 递归实现：
以树 father 为根的 01 字符串 s，得到孩子的各段 01字符串s1[1], s1[2], …, s[n], 用vector 来存，用sort 排序，
再拼接，得到的是father 为根的01字符串的最小表示

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
string a, b;
int Test;string dfs(string &s)	// 树 s 从坐标u开始的最小表示
{
    if(s == "01"){
    return s;}int sum = 0;vector<string> tmp;int size = s.size();string str = "";for(int u = 1; u < size - 1; ++u){
    if(s[u] == '0'){
    str += '0';--sum;}else{
    str += '1';++sum;if(0 == sum){
    str = dfs(str);tmp.push_back(str);str = "";}}}sort(tmp.begin(), tmp.end());string s1 = "";size = tmp.size();for(int i = 0; i < size; ++i){
    s1 += tmp[i];	}s = '0' + s1 + '1';return s;
}int main()
{
    scanf("%d", &Test);while(Test--){
    cin >> a >> b;a = '0' + a + '1', b = '0' + b + '1';if(dfs(a) == dfs(b)){
    cout << "same" << endl;}else{
    cout << "different" << endl;}}return 0;
}/* 2 0010011101001011 0100011011001011 0100101100100111 0011000111010101 *//* same different */