AcWing 5740. 满树的遍历
原题链接
中等
作者:
一路生花AC
,
2025-04-17 19:18:40
· 甘肃
,
所有人可见
,
阅读 4
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 100010;
int n,root;
bool flag;
int ans;
vector<int> v[N],p;
void dfs(int u)
{
if(ans != v[u].size() && v[u].size())
{
flag = true;
}
ans = max(ans,(int)v[u].size());
p.push_back(u);
for(int i = 0;i < v[u].size();i ++ )
{
dfs(v[u][i]);
}
}
int main()
{
cin >> n;
for(int i = 1;i <= n;i ++ )
{
int x;
cin >> x;
if(x == 0)root = i;
else v[x].push_back(i);
}
ans = max(ans,(int)v[root].size());
dfs(root);
if(flag)
{
cout << ans << " " << "no" << endl;
for(int i = 0;i < p.size();i ++ )cout << p[i] << " ";
cout << endl;
}else
{
cout << ans << " " << "yes" <<endl;
for(int i = 0;i < p.size();i ++ )cout << p[i] << " ";
cout << endl;
}
return 0;
}