ARC171-C Swap on Tree が理解できたかもしれない

はじめに

問題は以下です。

https://atcoder.jp/contests/arc171/tasks/arc171_c

この記事は本番中に通せなかった AtCoder Regular Contest 171 C問題 - Swap on Tree の解き方の解釈を与えたものです。

この問題は自分にとってかなり苦手で、なぜこんなにも正解者が多かったのかは今でも理解できません。とりあえず解説を読んでから数時間考えた末に思いついた方法を載せます。これよりもっと簡単に解く方法があれば知りたいです。

STEP 1

辺に注目

ある辺に注目して、それを $e$ と置きます。辺 $e$ を使用した場合、駒がスワップされた後に辺 $e$ は削除され、木は $2$ つの連結成分に別れます。

その後、異なる連結成分の頂点はもう交換されることはありません。

辺 $e$ を削除した後のそれぞれの連結成分に属する頂点を $A, B$ グループと考えてみます。

もし操作中に辺 $e$ を使用しない場合, 最初から辺 $e$ は無いものとして構わないでしょう。よって、すべての操作にわたって $A$ グループと $B$ グループの頂点が交換されることはありません。

もし操作中に辺 $e$ を使用する場合、 $A$ グループの何らかの頂点と、 $B$ グループの何らかの頂点を交換した後に辺 $e$ を削除します。

つまり、操作後の状態において、もとの $A$ グループの中に $B$ グループの頂点が $1$ つ入り込んでいる状態になります。もとの $B$ グループの中にも $A$ グループの頂点が $1$ つ入り込んでいます。

辺 $e$ を使用した場合と使用していない場合とで、もとの $A$ グループの中に $B$ グループの頂点が入り込んでいるかどうかが異なります。よって、確実に数列 $(a_1, a_2, \cdots, a_N)$ が違うということが分かります。

問題の言い換え

辺 $e$ に注目するのをやめて、すべての辺のそれぞれについて「使用する / 使用しない」を決めたとします。

使用する辺の集合によって出来上がる数列 $(a_1, a_2, \cdots, a_N)$ はすべて異なる、と感じることができます。

実際にこれは簡単に証明できます。使用する辺の集合を $S_1, S_2$ として、 $S_1 \ne S_2$ とします。このとき、（一般性を失わず） $S_1 \backslash S_2 \ne \emptyset$ とします。すると、 $e \in S_1 \backslash S_2$ を $1$ つ取ることができます。 $S_1$ では辺 $e$ は使用しますが、 $S_2$ では辺 $e$ は使用しません。さきほど考察したように、ある辺を「使用した / 使用しない」で数列 $a$ は必ず異なります。よって、出来上がる数列 $a$ は $S_1, S_2$ で異なります。これが任意の $S_1, S_2$ $(S_1 \ne S_2)$ で成り立つため、使用する辺の集合によって出来上がる数列 $a$ の集合はすべて異なります。

よって、使用する辺集合を固定して、その場合に解けばよいことが分かります。使用する辺集合によって連結成分が別れている場合、それらの連結成分が関わることはありません。よって、辺集合に対するありえる数列 $a$ の個数は、それぞれの連結成分について操作した場合の掛け算になります。

よって、使用する辺集合は連結、とくに木の「すべての辺を使用する」場合を考えればいいことが分かります。制約は一旦ほっといて、これによって問題が「すべての辺を使用する」場合に帰着されました。

STEP 2

すべての辺を使用する場合を考えます。まず、出来上がる数列は残念ながら $1$ 通りでも $(N-1)!$ 通りでもありません。辺を操作する順番が違っていても、数列 $a$ が同じになる場合があります。

操作順序が違っていても得られる数列が同じになる場合があるというのは嬉しくありません。このとき、操作順序ではなく、「数列 $a$ に対して、それがありえるのはどういうときか？」を考えます。

駒の「流れ」

ある頂点 $v$ を固定して、駒 $v$ の行き先を $w$ とします。駒 $v$ を頂点 $w$ に運ぶには、 $v \to w$ のパスをとって、パス上ではこの順に運ぶ必要があります。

また、頂点 $v$ から頂点 $w$ に駒を運んでいるときは、他の辺に邪魔されてはいけません。

これが「頂点 $v$ の駒を頂点 $w$ に運ぶ」ための必要十分条件です。

そして、「パス上ではこの順に運ぶ必要がある」「他の辺に邪魔されてはいけない」の条件をまとめると、たとえば、↓の頂点のまわりの辺では、「1stの直後に2ndが来ないといけない」となります。

始点 $v$ においては、「その周りで1stを最初に使う」、終点 $w$ においては、「その周りで3rdを最後に使う」となります。つまり、通る頂点それぞれに対して、その頂点の周りの相対順序を $1$ 個定めています。

1対1対応

ここで、頂点 $v$ の固定を外して、すべての流れを見てみます。

すべての頂点からの「流れ」が見えます。さきほどの必要十分条件に従って、ある頂点の周りに注目すると、その相対順序は必ず $1$ 通りに定まることが分かります。

「とりうる数列 $a$ 」に対して、こういう現象が、すべての頂点の周りについて起こります。すなわち、すべての頂点の周りの辺について、使う順番が決まります。

ここからもとの「流れ」は復元できます。「始点」は1stの辺に流れます。流れ着いた点の周りに、その直後に使う辺があれば、そこに流れます。なければ、そこが終点になります。

よって、ありえる数列 $a$ →「それぞれの頂点の周りの使う辺の順序」→ ありえる数列 $a$ が一意に定まることが分かりました。

問題なのが、「その頂点の周りの使う辺の順序」を自由に決めると、それに対応する数列 $a$ は「ありえる数列」か？ということです。すなわち、「その頂点の周りの使う辺の順序」を自由に決めると、それに従う「使う辺の順序」が取れるか？ということです。直感的には取れそうです。

もしそうなら、ありえる数列 $a$ と「それぞれの頂点の周りの使う辺の順序」との一対一対応（全単射）が取れて、代わりに「それぞれの頂点の周りの使う辺の順序」を数え上げればいいことになります。

「その頂点の周りの使う辺の順序」に従う「使う辺の順序」が取れるか

「最初に使う辺」はどれがいいでしょうか？使う辺の両端の頂点において、その辺がどちらも 1st であればよいです。それぞれの頂点から 1st の辺のみを伸ばした有向グラフを考えます。

これは functional graph で、閉路は必ず存在します。しかし、もとのグラフが木の構造をしているので、閉路は必ず長さ $2$ となります。その閉路を取ればよいです。今回は $3$ つありますが、どれでもよいです。

その辺を使ったあとを考えます。まず、辺によって連結成分に分断します。ある頂点について、その頂点の周りのすべての辺を使い切った場合、その頂点を捨てるとします。

生きている頂点については、また1stを考えると functional graph となるのでこの操作を繰り返すことができます。最後はすべての辺を使い切ります。

よって、「それぞれの頂点の周りの使う辺の順序」→ ありえる！数列 $a$ が対応する、ということが分かりました。

答え

ありえる数列 $a$ と「それぞれの頂点の周りの使う辺の順序」との一対一対応（全単射）が取れたので、それぞれの頂点の周りの辺の順序を独立に定めることができます。

頂点 $v$ の次数を $\deg(v)$ とすると, $v$ の周りの辺の順序の決め方は $(\deg(v))!$ 通りあります。

よって、 $\prod_{v} (\deg(v))!$ が答えになります。

STEP 3

DP

「すべての辺を使う場合」は、 $\prod_{v} (\deg(v))!$ が答えです。実際に答える際は、使う辺の集合 $2^N$ 通りを指定しないといけないように見えますが、この場合何らかの木DPができそうに見えます。

適当に木を順序付けて有向木とします。頂点 $v$ に対して「 $v$ の子を根とする部分木たちに対する情報」から「 $v$ の情報」を得たいです。

$v$ の子 $w$ について、その頂点を使う場合、 $w$ の次数が $1$ 個増えます。木DPをする場合、 $N \le 3000$ という制約によって「二乗の木DP」が許されます。よって、情報として、「根で使っている辺の次数」を持っておいてもよいでしょう。

$\text{dp}_{i,j}$ を, 「頂点 $i$ を根とする部分木であって、現在根で使っている辺の次数が $j$ であるとき、その答えの総和」とおきます。

各 $v$ の子 $w$ について、

$v$ と $w$ の間の辺を使う場合、 $v$ の次数は $1$ 増え、 $w$ の次数は $1$ 増えて継承される。もとの $v$ の次数を $i$ , $w$ の次数を $j$ とした場合、STEP 2 で導いた $\prod_{v} (\deg(v))!$ に従って、その差分を計算すると、新しい $\text{dp}_{v}$ の状態 $i+1$ に $\text{dp}_{v,i}\times (i+1)\times \text{dp}_{w,j}\times (j+1)$ が加算される。
$v$ と $w$ の間の辺を使わない場合、次数はどちらも増えず継承される。新しい $\text{dp}_{v}$ の状態 $i$ に $\text{dp}_{v,i} \times \text{dp}_{w,j}$ が加算される。