P10477 Subway tree systems 题解,c++ 树相关题目

题目

poj 链接
洛谷链接

$n$ 组数据，每组数据给定两个 $01$ 串（长度不超过 $3000$），意思如下：

• 对于每一个 $0$，代表该节点有一个子节点，并前往该子节点。
• 对于每一个 $1$，代表返回该节点的父亲节点。

求两个字符串说表示的树是否同构。

思路

考虑对于每一个节点进行递归处理（因为可以知道一个大问题可以拆成多个小问题进行计算）。为方便后续操作，可虚构一个根节点的父亲节点（即在字符串开头加上 $0$，结尾加上 $1$）。

对于每一个节点，我们可以获得一个字符串代表该节点的子树，首先去掉头尾的字符（即去掉通往父亲节点的边），记 $S$ 为字符串，$cnt$ 表示 $S$ 从 $0$ 到 $i$ 中 $0$ 的数量与 $1$ 的数量的差，$j$ 表示儿子的数量。容易得到以下结论：

• 对于$S_i=0$,则 $cnt\leftarrow cnt+1$。
• 对于$S_i=0$,则 $cnt\leftarrow cnt-1$。
• 对于 $cnt=0$，即一个儿子已经遍历结束，则 $j\leftarrow j+1$，并统计前一个儿子所代表的子串进行递归。

如果全部儿子所代表的子串递归完毕，可按照字符串排序的方式排列儿子所代表的字符串，并在头尾添上 $01$。可以发现，对于两个同构的树，以上操作后获得的字符串相等。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T;
string a,b;
string paixu(string x) {//cout<<x<<endl;// 分离操作string y = x;int num = x.size(),cnt = 0;x = "";if(num <= 2) return y;for(int i = 1;i < num - 1;i++) x += y[i];num -= 2;string new_string[1505];int j = 1;for(int i = 0;i < num;i++) {if(x[i] == '0') cnt++,new_string[j] += '0';else cnt--,new_string[j] += '1';if(cnt == 0) {j++;}}j--;//递归for(int i = 1;i <= j;i++) new_string[i] = paixu(new_string[i]);//排序for(int i = j;i >= 1;i--) {for(int k = 1;k < i;k++) {if(new_string[k] > new_string[k + 1]) swap(new_string[k],new_string[k + 1]);}}for(int i = 2;i <= j;i++) new_string[1] += new_string[i];//cout<<("0" + new_string[1] + "1")<<endl;return ("0" + new_string[1] + "1");
}
signed main() {scanf("%lld",&T);while(T--) {cin >> a >> b;a = "0" + a + "1";b = "0" + b + "1";if(paixu(a) == paixu(b)) printf("same\n");else printf("different\n");}return 0;
}