求树的最小表示,本题可以简化成给你两个dfs序列让你判断他们的最小表示是否相同,用递归来做,最开始u过滤当前的0,当前节点为0的时候说明还可以继续往下dfs,结束后u过滤当前的1,在用数组保存和排序走过的节点的最小表示,数组最后记得要加上1。
C++ 代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
typedef long long ll;
const int N=1e5+10,INF=1e8;
string dfs(string &a, int &u)
{
u++;
vector<string> aa;
while (a[u]=='0') aa.push_back(dfs(a,u));
u++;
sort(aa.begin(),aa.end());
string res="0";
for (auto t:aa) res+=t;
res+='1';
return res;
}
int main()
{
int t;
cin>>t;
while(t--)
{
string a,b;
cin>>a>>b;
a='0'+a+'1';
b='0'+b+'1';
int ua=0,ub=0;
string a1=dfs(a,ua);
string b1=dfs(b,ub);
if(a1==b1) cout<<"same"<<endl;
else cout<<"different"<<endl;
}
return 0;
}