主要思路:最小表示相同的树就是同构的
为什么难度评级是简单啊,我最后还是看了sol才过的【快哭了】真的是我tcl吗【快哭了】
一开始我想的是,字典序最小就是一开始0尽可能多,所以对于每个点按照其子树内最长链长度从大到小选择子节点。然后getWA。。
原因是对于两个最长链长度相同的子节点,要选择子节点的子节点最长链尽可能的长。但这样就很难实现了。
于是我去看了sol。
对于点u,假设其所有子节点v的最小表示已知,其最小表示则为所有v的最小表示按字典序从小到大拼起来。
显然递归处理即可。
//Wan Hong 2.2
//home
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
typedef long long ll;
typedef std::pair<ll,ll> pll;
typedef std::string str;
#define INF (1ll<<58)
ll read()
{
ll f=1,x=0;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
ll max(ll a,ll b)
{
return a>b?a:b;
}
ll min(ll a,ll b)
{
return a<b?a:b;
}
bool umax(ll& a,ll b)
{
if(b>a)return a=b,1;
return 0;
}
bool umin(ll& a,ll b)
{
if(b<a)return a=b,1;
return 0;
}
/**********/
#define MAXN 5011
str a,b;
ll xa,xb;
str min_tree(str a,ll &x)//求解树的最小表示
{
std::vector<str>v;
++x;
str ans="0";
while(a[x]=='0')v.push_back(min_tree(a,x));
++x;
std::sort(v.begin(),v.end());
for(std::vector<str>::iterator it=v.begin();it!=v.end();++it)ans+=*it;
ans+='1';
return ans;
}
void work()
{
std::cin>>a>>b;
a='0'+a+'1';b='0'+b+'1';
xa=0,xb=0;
if(min_tree(a,xa)==min_tree(b,xb))puts("same");
else puts("different");
}
int main()
{
ll t=read();
while(t--)work();
return 0;
}