标签：同构 括号 int BJOI2015 t1 55 fa 模板
- 一段合法的括号序和一棵有根树唯一对应，具体而言，考虑生成括号序的过程，从根节点出发，遇到左括号就向下走一步，遇到右括号就向上走一步
- 由于树上的一个节点可能有多个子节点，因此在不规定访问顺序的情况下，同一棵树有多种不同的括号序列
点击查看代码
#include <bits/stdc++.h>
using namespace std;
vector<int>a[55];
string f[55];
vector<string>c[55];
int n,ans[55];
struct t1
{
string s;
int id;
}t[55];
bool cmp(t1 a,t1 b)
{
if(a.s!=b.s)
{
return a.s<b.s;
}
return a.id<b.id;
}
void dfs(int n1,int fa)
{
c[n1].clear();
for(int i=0;i<a[n1].size();i++)
{
if(a[n1][i]!=fa)
{
dfs(a[n1][i],n1);
c[n1].push_back(f[a[n1][i]]);
}
}
sort(c[n1].begin(),c[n1].end());
f[n1]="(";
for(int i=0;i<c[n1].size();i++)
{
f[n1]+=c[n1][i];
}
f[n1]+=")";
}
int main()
{
int m;
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>n;
for(int j=1;j<=n;j++)
{
a[j].clear();
}
for(int j=1;j<=n;j++)
{
int fa;
cin>>fa;
if(fa==0)
{
}
else
{
a[fa].push_back(j);
a[j].push_back(fa);
}
}
t[i].id=i;
for(int j=1;j<=n;j++)
{
dfs(j,0);
if(t[i].s=="")
{
t[i].s=f[j];
}
t[i].s=min(t[i].s,f[j]);
}
}
sort(t+1,t+m+1,cmp);
t[0].s="";
for(int i=1;i<=m;i++)
{
if(t[i].s!=t[i-1].s)
{
ans[t[i].id]=t[i].id;
}
else
{
ans[t[i].id]=ans[t[i-1].id];
}
}
for(int i=1;i<=m;i++)
{
cout<<ans[i]<<endl;
}
return 0;
}
标签：同构,
括号,
int,
BJOI2015,
t1,
55,
fa,
模板
From： https://www.cnblogs.com/watersail/p/18281621