問題設定がややこしい。
https://beta.atcoder.jp/contests/arc095/tasks/arc095_d
問題
1~NのPermutationを成す数列Aに対し、以下のように木を成すグラフを作る。
1より大きいA[i]に対し、A[j]<A[i]となるjのうち最大のものを求め、iとjの間に辺を張る。
木を成すグラフが与えられる。
この木と同型のグラフを構築できるAのうち辞書順最小のものを求めよ。
解法
まずこのPermutationによるグラフの生成法だが、直径を成す頂点群のうち両端以外の頂点に何本か長さ1の分岐があるようなグラフを生成できる。
(解説によるとキャタピラグラフというらしい)
そこで、まず与えられる木がキャタピラグラフかを求めよう。
これはまず直径を求めた後、直径上にある頂点群が持つ辺の数を数えれば判定できる。
直径を成す頂点群において、直径以外の辺の数を順に並べてみる。
例えばテストケース1ならP=(0,0,2,0)である。(反転した方が辞書順最小なら反転する)
ここから直径の頂点i毎に端から以下のように数列を作っていこう。
未登場の頂点番号の最小値をXとする。Xの手前にP[i]個Xより大きな要素を置き、Xのあとに1個Xより大きい要素を置く。
例えばP[i]=2なら(X+1) (X+2) X (X+3)と置けばよい。あとはP[i+1]を処理するときは(X+4)から継続する。
int N; vector<vector<int>> E; pair<int,int> farthest(vector<vector<int>>& E, int cur,int pre,int d,vector<int>& D) { D[cur]=d; pair<int,int> r={d,cur}; FORR(e,E[cur]) if(e!=pre) r=max(r, farthest(E,e,cur,d+1,D)); return r; } vector<pair<int,int>> diameter(vector<vector<int>>& E) { // diameter,center vector<int> D[2]; D[0].resize(E.size()); D[1].resize(E.size()); auto v1=farthest(E,0,0,0,D[0]); auto v2=farthest(E,v1.second,v1.second,0,D[0]); farthest(E,v2.second,v2.second,0,D[1]); vector<pair<int,int>> R; //重心を取る場合 for(int i=E.size()-1;i>=0;i--) if(D[0][i]+D[1][i]==v2.first) R.push_back({D[0][i],i}); sort(ALL(R)); return R; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; E.resize(N); FOR(i,N-1) { cin>>x>>y; E[x-1].push_back(y-1); E[y-1].push_back(x-1); } auto R=diameter(E); vector<int> A,B; int num=0; FOR(i,R.size()) { A.push_back(E[R[i].second].size()); A.back()--; if(i>0 && i<R.size()-1) A.back()--; num+=1+A.back(); } B=A; reverse(ALL(B)); if(num!=N) return _P("-1\n"); A=min(A,B); int nex=0; FOR(i,A.size()) { FOR(x,A[i]) cout<<nex+2+x<<" "; cout<<nex+1<<" "; nex+=1+A[i]; } cout<<endl; }
まとめ
キャタピラグラフになることに気づけば難しくない。