ARC095 F : Permutation Tree(900)
作成日：2018.09.09
最終更新日：2018.09.09
問題概要
$1$から$n$の順列$p_1,p_2,...,p_n$と頂点$1,2,...,n$から手順「$p_i \gt 1$である各$i$において$p_j \lt p_i$となる最大の$j$をとり、頂点$i,j$間に辺を張る」によって木を生成する。
$n$頂点からなり$v_i$と$w_i$の間に辺がある木と同型な木を生成するような順列が存在するかを判定せよ。
また可能であれば、そのような順列のうち辞書順最小のものを求めよ。
制約
$2 \leq n \leq 10^5$
$1 \leq v_i,w_i \leq n$
与えられるグラフは木
考え方
頂点$i$と辺で結ばれている頂点について考える。
まず$p_i \neq 1$であれば、手順により1つの頂点と結ばれる。
また$j$における手順によって頂点$j$と結ばれる条件は、$p_i \lt p_j$かつ$p_k \lt p_j$,$k \gt i$を満たす$k$が存在しない時である。
もし$i = n$であれば、そのような$j$は$(n-p_i)$個存在する。
逆に$p_i \lt p_j$ならば$p_k \lt p_j$が常に成り立つ、すなわち$p_k \lt p_i$を満たす$k$($\gt i$)が存在するならば、そのような$j$は1つも存在しない。
後者を満たす$i$($\neq 1$に注意)において、頂点$i$は次数$1$であることが分かる。
またこのような$p_i$を数列から消すと、残った数列は単調増加となる。
さらに、そこに残った先頭以外の要素(先頭の要素は$1$であることに注意)において手順を行った時に選ばれる要素は、残った数列においての直前の要素である。
以上より順列から作れる木は、次数$1$の要素を除けば枝分かれがない木に限定されることが分かる。
今度は次数$1$の要素を除けば枝分かれがない木を与えられた時に、それを生成するような順列を構築することを考える。
まずは、先の考察のように$k \gt i$,$p_k \lt p_i$を満たす要素を除いた数列($q$とする)を作ることにする。
除かれた要素において手順により選ばれる回数を考えると、$q_i$に対応する頂点と結ばれている除かれた要素に対応する頂点の数を$u_i$とすると$q_{i+1}-q_i-1=u_i$($q_{i+1}$が存在しない場合はそれをn+1とみなす)でなければならない。
よって枝分かれがない部分とその向きを決めれば、$q$は一意に定まる($q_1 = 1$に注意)。
後は除かれた要素を元に戻せば良いが、これは自身より小さい要素が後に出てくるような位置であればどこでも良い。
最後にこのような順列を辞書順最小となるように作ることを考える。
$q_1 = 1$であるが、これより前に要素を置かなくて良いならばそのほうが良い。
これは$q_2 = 2$として、$q_1$に次数$1$の頂点を対応させることで達成できる。
同様に、$q$の末尾を$n$にするために、それにも次数$1$の頂点を対応させることにする。
次数$2$以上の頂点には対応する$q$の要素が存在しなければならないが、その枝分かれしない部分の両端に次数$1$の頂点を加えても$q$を構成できるので問題ない。
また除かれた要素を置ける位置の制約から、これらはできるだけ後ろに置いたほうが良いことが分かる。
さらに$q_i$と$q_{i+1}$の間に置かれた要素は昇順にするべきである。
以上より順列は$q_1,q_2+1,q_2+2,...,q_3-1,q_2,...$というようにするべきであることが分かる。
また$q$を決めるためには枝分かれしない部分の向きを定める必要があるが、これは$u_i$を並べた時に辞書順で小さくなる向きを選べば良い。
ソースコード
マクロ等はこちら
const int MC = 1e5 + 3;
int n;
vector<int> V[MC];
int main(){
cin >> n;
repp(i,1,n){
int a,b; cin >> a >> b;
V[a].push_back(b);
V[b].push_back(a);
}
if(n == 2) return cout << "1 2" << endl , 0;
int w;
repp(i,1,n+1){
int c = 0;
for(auto z : V[i]) if(V[z].size() > 1) ++c;
if(c > 2) return cout << -1 << endl , 0;
if(V[i].size() > 1 && c <= 1) w = i;
}
vector<int> u;
int pr = 0;
while(w){
u.push_back(V[w].size()-2);
int nx = 0;
for(auto z : V[w]) if(z != pr && V[z].size() > 1) nx = z;
pr = w; w = nx;
}
repp(i,0,u.size()) if(u[i] != u[u.size()-1-i]){
if(u[i] > u[u.size()-1-i]) reverse(u.begin(),u.end());
break;
}
int s = 2;
cout << 1 << ' ';
for(auto z : u){
repp(i,s+1,s+z+1) cout << i << ' ';
cout << s << ' ';
s += z+1;
}
cout << n << endl;
return 0;
}解法まとめ
次数$1$の要素を除けば枝分かれがない木でなければ、条件を満たす順列は存在しない。(16,17行)
そうでなければ順列を構成できる。
枝分かれがない部分のうち次数$2$以上の頂点を並べる。(20-27行)
頂点の代わりに(頂点の次数)$-2$を並べた数列$u$の辞書順が小さくなるような向きにする。(28-31行)
$q_1 = 1$,$q_2 = 2$,$q_{i+1} = q_i + u_i + 1$($i \geq 2$)とし、数列$q$の2つの要素$q_{i-1}$と$q_i$($i \geq 2$)の間に$q_i+1$から$q_{i+1}-1$を昇順に並べたものが答えである。(32-39行)
但し上のコードでは、念のため次数$2$以上の頂点がない$n=2$の場合を別で処理した(13行目で$w$を$0$で初期化しておけば場合分けは不要だがちょっと怖い)。(12行)