yukicoder 275 - Kiri8128の日記

良問揃いですごいです。

ABCF の 4 完9位です！（嘘です、 F はテスターをしてました。）

DE は後で解きましたが面白かったです。

解説と似てますが、全方位木 DP の状態の持ち方を工夫すると簡単になった気がしたので書いておきます。

特に「子の中で最大」みたいな処理が rerooting をすると崩れるので、最大から2番目のもの（ $v$ の隣接頂点の中で最大から2番目のものを ${\rm MAX2}_v$ みたいに書きます）も持つようにしています。

頂点 $i$ を根とする部分木に対して、次の 4 状態に分類することを考えます。 $i$ の親を $p$ とします。

状態0

$p$ から $i$ に行ったあと、部分木の頂点をすべて通って再び $p$ に戻れる

状態2

$p$ から $i$ に行ったあと、部分木の頂点をすべて通れる（が $p$ には戻れない）

かつ $i={\rm MIN}_p$ または $i={\rm MAX}_p$

状態3

$p$ から $i$ に行ったあと、部分木の頂点をすべて通れる（が $p$ には戻れない）

かつ $i={\rm MAX2}_p$

状態4

上記以外

状態番号が穴あきな理由は、合計が4以上ならアウト、みたいなことがやりやすいので。

状態2と状態3の違いは、状態2はどの頂点からスタートしたとしても $p$ から $i$ を最後の辺にできるのに対して、状態3では最初に $MAX_p$ 方向から $p$ に来た場合のみ $i$ 方向を最後の辺にできます。

この状態の決定は根の選び方によらないので、 rerooting をしても結果が使い回せます。（つまりライブラリの設定をいじるだけで解けます。）

この記事の言葉で言うと、次のように設定すれば良いです。

単位元は0
マージは単に状態番号の和を取ります
Adjust は、 Bottom Up については
- 状態番号の合計が4以上ならアウト（状態4）
- 状態番号の合計が3のときは、親が ${\rm MAX}_i$ と一致しなければアウト（状態4）
- 状態番号の合計が0かつ親に戻れる（ $p = {\rm MIN}_i$ ）ときはOK（状態0）
- それ以外のときは子の id が親の隣接頂点の最大または最小のときは状態2、大きい法から2番目のときは状態3にします。
Top Down の方もこれと同様です
最後の調整 Adj_Fin は、状態番号の合計が2以下なら "Yes" 、そうでなければ "No" です。

これを愚直に書けば良いです（AC コードの29～40行目）。実質10行程度ですね。

これ以外は出力も含めてライブラリそのままで動きます *1。

*1:adj_bu の引数に p がなかったのでそこだけ追加しました