Submission #19309608

---

Source Code Expand

#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define debug(x) cout << #x << ": " << (x) << endl
#else
#define debug(x)
#endif
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int maxn=1e6+7,inf=0x3f3f3f3f,mod=1e9+7;

int fa[maxn],dep[maxn],n,s[maxn],p1[maxn],p2[maxn],np[maxn],top;
vi g[maxn];;

void dfs(int u,int f)
{
    fa[u]=f;
    dep[u]=dep[f]+1;
    for(auto &v:g[u])
    {
        if(v==f) continue;
        dfs(v,u);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=0,u,v;i<n-1;++i)
    {
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    int x=0,y=0;
    for(int i=1;i<=n;++i) if(dep[i]>dep[x]) x=i;
    dfs(x,0);
    for(int i=1;i<=n;++i) if(dep[i]>dep[y]) y=i;
    for(int i=y;i;i=fa[i]) s[i]++;
    for(int i=1;i<=n;++i)
    {
        if(!s[i] && ++s[fa[i]]==1)
        {
            cout<<"-1\n";
            return 0;
        }
    }
    vi a;
    for(int i=y;i;i=fa[i]) a.push_back(s[i]);
    top=0;
    for(auto &s:a)
    {
        np[top+1]=top+s;
        for(int j=1;j<s;++j) np[top+1+j]=top+j;
        top+=s;
    }
    for(int i=1;i<=n;++i) p1[np[i]]=i;
    reverse(a.begin(),a.end());
    top=0;
    for(auto &s:a)
    {
        np[top+1]=top+s;
        for(int j=1;j<s;++j) np[top+1+j]=top+j;
        top+=s;
    }
    for(int i=1;i<=n;++i) p2[np[i]]=i;

    int id=1;
    while(p1[id]==p2[id] && id<=n) id++;
    if(p1[id]<p2[id]) for(int i=1;i<=n;++i) cout<<p1[i]<<' ';
    else for(int i=1;i<=n;++i) cout<<p2[i]<<' ';
    cout<<'\n';
    return 0;
}

Submission Info

Judge Result