ARC095 F - Permutation Tree -
問題
解法
まず、数列から木を作ってみる。
作ると木に頂点を追加するときは、脚を増やすか胴体を伸ばす選択肢しかないことが分かる。
（こういう木をcaterpillarというらしい。確かに毛虫っぽい。）
なぜ、caterpillarになるのかのイメージは公式の動画解説が分かりやすい。
数列から作られる木はcatapillarなので、 与えられる木がcatepillarだったらそれから作ることができる辞書順最小の数列を出力、そうではなかったら−１を出力すればいい。
数列の作り方として、
1はどこに置いても変わらないので最初に置いたほうがいい。
それ以外の数字もできるだけ小さいのからつかっていきたい。
caterpillarと数列の関係性を見ると、脚は順序が逆転してる頂点間に生えている。
上記の考察から胴体は小さい順につなげていき、脚が生えていたらその脚の数分の数字を、脚の生えている頂点より左に置くという感じで数列を構成していく。
胴体が木の直径であることは直感的に分かる。数列の構成の仕方として２パターン考えられるが（直径の端は２つあるので）、その２つのうち、辞書順で小さい方を最終的に出力すればいい。
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if ( a > b ) a = b; } template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if ( a < b ) a = b; } using Pii = pair<int, int>; const int INF = 1e18; struct Edge { int t, w; Edge(){} Edge(int t, int w): t(t), w(w) {} }; vector<Edge> G[100001]; int n, d[100001]; int st, ds; void bfs(int s) { for ( int i = 0; i < n; i++ ) d[i] = INF; queue<int> q; q.push(s); d[s] = 0; int u; while ( !q.empty() ) { u = q.front(); q.pop(); for ( int i = 0; i < (int)G[u].size(); i++ ) { Edge e = G[u][i]; if ( d[e.t] == INF ) { d[e.t] = d[u]+e.w; q.push(e.t); } } } } void calc_d() { bfs(0); int maxv = 0; st = 0; ds = 0; for ( int i = 0; i < n; i++ ) { if ( d[i] == INF ) continue; if ( maxv < d[i] ) { maxv = d[i]; st = i; } } bfs(st); maxv = 0; for ( int i = 0; i < n; i++ ) { if ( d[i] == INF ) continue; if ( maxv < d[i] ) { maxv = d[i]; ds = i; } } } int pre[100001]; bool is_body[100001]; vector<int> path; void calc_path(int v, int p) { pre[v] = p; for ( int i = 0; i < (int)G[v].size(); i++ ) { Edge e = G[v][i]; if ( e.t == p ) continue; calc_path(e.t, v); } } bool is_caterpillar() { for ( int i = 0; i < (int)path.size(); i++ ) { for ( int j = 0; j < (int)G[path[i]].size(); j++ ) { int v = G[path[i]][j].t; if ( is_body[v] ) continue; if ( (int)G[v].size() > 1 ) return false; } } return true; } signed main() { cin >> n; for ( int i = 0; i < n-1; i++ ) { int v, w; cin >> v >> w; v--; w--; G[v].push_back(Edge(w, 1)); G[w].push_back(Edge(v, 1)); } calc_d(); calc_path(st, -1); { int v = ds; while ( v != -1 ) { path.push_back(v); is_body[v] = true; v = pre[v]; } } if ( !is_caterpillar() ) { cout << -1 << endl; exit(0); } vector<int> ans1, ans2; int idx = 1; for ( int i = 0; i < (int)path.size(); i++ ) { int tmp = idx; idx++; for ( int j = 0; j < (int)G[path[i]].size(); j++ ) { int v = G[path[i]][j].t; if ( is_body[v] ) continue; ans1.push_back(idx++); } ans1.push_back(tmp); } idx = 1; for ( int i = (int)path.size()-1; i >= 0; i-- ) { int tmp = idx; idx++; for ( int j = 0; j < (int)G[path[i]].size(); j++ ) { int v = G[path[i]][j].t; if ( is_body[v] ) continue; ans2.push_back(idx++); } ans2.push_back(tmp); } vector<int> ans = min(ans1, ans2); for ( int i = 0; i < n; i++ ) { if ( i ) cout << " "; cout << ans[i]; } cout << endl; return 0; }
