Codeforces Round #614 (Div. 1) C. Xenon's Attack on the Gangs

お題箱より。

Problem - C - Codeforces

問題概要

$n$ 頂点の木が与えられる。この木の辺に $0, 1, ..., n-2$ の値を1つずつ割り振ることを考える。

異なる2頂点 $u, v$ に対して $mex(u, v)$ を「 $u, v$ 間パスに含まれる辺の値として登場しない最小の非負整数」と定義する。そして値の割り振り方のスコア $S$ を

$S = \displaystyle \sum_{1 \le u \lt v \le n} mex(u, v)$

と定義する。 $S$ の最大値を求めよ。

制約

$2 \le n \le 3000$
与えられるグラフは木である

解法

スコア $S$ は、以下の値を全て合計したものとして計算できます。

$s_{1} =$ パスに $0$ を含む2頂点のペアの個数
$s_{2} =$ パスに $0, 1$ を含む2頂点のペアの個数
$s_{3} =$ パスに $0, 1, 2$ を含む2頂点のペアの個数
....

なぜなら $mex(u, v)$ がある値 $k$ である必要十分条件は、 $u, v$ 間のパスに $0, 1, ..., k-1$ が全て含まれていてかつ $k$ が含まれていないことであり、このようなペアは上記の計算方法で $s_{1}, ..., s_{k}$ のちょうど $k$ 回数えられるからです。

スコアをなるべく大きくするには、値 $0, 1, 2, ...$ を割り振る辺をなるべく一直線に並べるのが得策です。具体的には

どこかの辺に値 $0$ を割り振る。
値 $1$ の辺は、値 $0$ の辺の両端どちらかに接続する辺から選ぶ。
値 $2$ の辺は、値 $0, 1$ の辺で作られるパスの両端どちらかに接続する辺から選ぶ。
...

という割り振り方を、パスの両端をもう伸ばせなくなる（つまり両端がともに葉である）まで続けるのが良いです。このような形になっていないもの、つまりまだパスを伸ばせるのに途中で非連結になったり枝分かれしているような割り振り方は、パスになるように組み替えることで解をより良くできることが示せます。

f:id:betrue12:20200502143837p:plain

値の割り振りルールをこのようなものに限定できることを利用して、スコアの最大値を求めるDPを考えます。アイデアは「短いパスから始めてだんだん長くしていく」という感じです。具体的には2頂点 $u, v$ に対して $dp\lbrack u \rbrack\lbrack v \rbrack$ を以下のように定義します。

頂点 $u, v$ 間のパスに含まれる辺を $d$ 本として、このパスの辺に $0, ..., d-1$ の値を割り振った時に得られる $s_{1} + \cdots + s_{d}$ の最大値

これを $d$ が小さいような2頂点ペアから順番に計算していきます。メモ化再帰でも良いでしょう。

$dp\lbrack u \rbrack\lbrack v \rbrack$ を計算する遷移を考えます。ここで $s_{d}$ の値は、パスによって分断された部分木を考えると「 $u$ 側の部分木に属する頂点の個数」×「 $v$ 側の部分木に属する頂点の個数」として計算できます。その前の $s_{1} + \cdots + s_{d-1}$ はDPの遷移元であり、その値は

$u$ 側に値 $d-1$ の辺を置く場合、 $u, v$ 間パスにおける $u$ の隣の頂点を $u^{\prime}$ として $dp\lbrack u^{\prime} \rbrack\lbrack v \rbrack$
$v$ 側に値 $d-1$ の辺を置く場合、 $u, v$ 間パスにおける $v$ の隣の頂点を $v^{\prime}$ として $dp\lbrack u \rbrack\lbrack v^{\prime} \rbrack$