ちょっとずつ★3.5のupsolveを進めていきます。今回扱うのはyukicoder contest 366 H問題 No.2115 Making Forest Easyです。公式解説は恐らく上級者向けに書かれており、筆者（$p$進大好きbot）の実力だとまだ理解できているか自信がなかったので、もう少し易しめの（ただし高速な言語向けの）解法を解説いたします。

なお参考までに、自信がないなりに公式解説の意図を推測してみた結果はこちらです。

• $T$の誘導部分グラフであって木をなすもの（$T,T_1,T_2,T_3$）を暗黙に、頂点$0$を$T$の根とみなした時に最も根に近い頂点を根とする根付き木として扱っている？（でないとその頂点$i$に対し$i$を根とする部分木が意図通りの意味に解釈されない気がするため）
• $dp1$などは、$T$ではなく$T$の誘導部分グラフであって木をなすものそれぞれに対して暗黙に定義しており、本来はどの木に考えているかに依存する概念だが$T_3$以外は全て省略して同じ記号で書いている？
• $T_3$に対する$dp1$などは暗黙に$newdp1$などと記載している？
• $newdp1$などに対する加算操作を全て代入操作であるかのように書いている？

解釈に飛躍がありすぎると思うので、間違っている可能性は十分高いです。その場合はすみません。

問題の概要

正確な問題文はこちらです。

木$T$の各頂点$i$に非負整数値スコア$A_i$が定義されており、$T$の誘導部分グラフである木のスコアはその頂点のスコアの最大値と頂点数の積で定義されており、$T$から好きなだけ辺を削除して得られる森のスコアはその各連結成分のスコアの総和として定義されている。 $T$から好きなだけ辺を削除して得られる森全体をわたる、スコアの総和をmod $998244353$で求めよ。

前置き

実行時間制限は4000[ms]で、$T$の頂点数$N$の上限は$5000$で、今回紹介する解法の計算量は$\Theta(N^2)$です。c++で適切に実装すれば1000[ms]以内に実行できますが、遅い言語を使ったり実装が冗長だったりするとTLEとなります。

解説

以下スコアを全て$\lvert \cdot \rvert$で表します。$T$の辺集合を$E$と置き、$E$の部分集合全体の集合を$P(E)$と置き、各$U \in P(E)$に対し$T$から$U$を削除して得られる森を$F_U$と置き、$T$の誘導部分グラフ$F$に対しその頂点集合と連結成分全体の集合をそれぞれ$V(F)$と$\pi(F)$と置きます。

求める値でmod $998244353$を取る前の値は、定義より

\[ \begin{array}{rcl} \sum_{U \in P(E)} |F_U| & = & \sum_{U \in P(E)} \sum_{T’ \in \pi(F_U)} |T’| \\
& = & \sum_{U \in P(E)} \sum_{T’ \in \pi(F_U)} \max_{i \in V(T’)} A_i \times \# V(T’) \end{array} \]

となります。何らかの意味で「$i$の寄与」を定義して最右辺を頂点ごとの寄与に分解したいです（同じ値で纏め上げるテクニック、広義の分割統治法）。そこで、最右辺を式変形して

\[ \sum_{i \in V(T)} c_i A_i \]

の形で表します（$c_i$は非負整数）。

ただし$A=(A_i)_{i \in V(T)}$には成分の重複がありうるので、係数列$c = (c_i)_{i \in V(T)}$は$T$の構造と$A$の成分間の大小関係だけでは一意に決まらないかもしれません。$c$を動的計画法で求めるために一意とは限らない$c$をうまく選択する目的で、$A$の代わりに重複のない$B = ((A_i,i))_{i \in V(T)}$を用います。

$B$を昇順にソートした配列（$A_i$側が同じである項の順序は好きに決めて良い）を$B’$と置きます。各$i \in V(T)$に対し$N$未満の非負整数$p_i$を、$B’$において$(A_i,i)$が第$p_i$成分となるように定めます。$N$未満の各非負整数$q$に対し、$q = p_i$を満たす一意な$i \in V(T)$を$\iota(q)$と置きます。

更に各$i \in V(T)$に対し、$U \in P(E)$であって$F_U$において$i$の連結成分を$T’$と置いた時$\{p_j \mid j \in V(T’)\}$の最大値が$p_i$であるもの全体の集合を$P_i$と置きます。各$U \in P_i$に対し、$F_U$における$i$の連結成分を$T_{i,U}$と置きます。

この時、

\[ \begin{array}{rcl} \sum_{U \in P(E)} |F_U| & = & \sum_{U \in P(E)} \sum_{T’ \in \pi(F_U)} (\max_{i \in V(T’)} A_i) \times \# V(T’) \\
& = & \sum_{U \in P(E)} \sum_{T’ \in \pi(F_U)} \max \{A_i \mid i \in V(T’)\} \times \# V(T’) \\
& = & \sum_{U \in P(E)} \sum_{T’ \in \pi(F_U)} A_{\iota(\max \{p_i \mid i \in V(T’)\})} \times \# V(T’) \\
& = & \sum_{i \in V(T)} \sum_{U \in P_i} A_{\iota(p_i)} \times \# V(T_{i,U}) \\
& = & \sum_{i \in V(T)} \left( \sum_{U \in P_i} \# V(T_{i,U}) \right) A_i \end{array} \]

となります。従って各$i \in V(T)$に対し

\[ c_i = \sum_{U \in P_i} \# V(T_{i,U}) \]

と定めれば良いです。更に$i$を根として$T$を根付き木と思ったものを$(T,i)$と置きます。各$j \in V(T)$に対し$j$を根とする$(T,i)$の部分木を$(T,i)_j$と置き、その辺集合を$E_{i,j}$と置き、$U \in P(E_{i,j})$であって$(T,i)_j$から$U$を除いて得られる森を$F_{i,j,U}$と置き、$F_{i,j,U}$において$j$の連結成分を$T’$と置いた時$\{P_k \mid k \in V(T’)\}$の最大値が$p_i$以下であるもの全体の集合を$P_{i,j}$と置き、各$U \in P_{i,j}$に対し、$F_{i,j,U}$における$j$の連結成分を$T_{i,j,U}$と置きます。この時

\[ \begin{array}{rcl} c_i & = & \sum_{U \in P_i} \# V(T_{i,U}) \\
& = & \sum_{U \in P_{i,i}} \# V(T_{i,i,U}) \end{array} \]

とも表せます。各$j \in V((T,i))$に対し

\[ \textrm{dp}_i[j] := \sum_{U \in P_{i,j}} \# V(T_{i,j,U}) \]

と定めれば$c_i = \textrm{dp}_i[i]$となります。任意の$j \in V((T,i))$に対し$\textrm{dp}_i[j]$は定義から

• $(T,i)_j$の切り分け方であって、$j$の連結成分を$T’$と置いた時$\{P_k \mid k \in V(T’)\}$の最大値が$P_i$以下となるようなもの全体をわたる$\# V(T’)$の総和

に他ならず、これは

• $(T,i)_j$の切り分け方であって、$j$の連結成分を$T’$と置いた時$\{P_k \mid k \in V(T’)\}$の最大値が$P_i$以下となるようなもの全体をわたる$1$の総和（切り分け方の総数）
• $(T,i)_j$の切り分け方全体をわたる$1$の総和（切り分け方の総数）

を並行して$(T,i)$上の木DPで求めていくことで$O(N)$で処理できます。

各$i \in V(T)$ごとに$c_i$を求めればよいので、合計$O(N^2)$で処理できました。

実装例

• c++: https://yukicoder.me/submissions/1113720

自分用覚え書き

github pagesで数式を使う際は、閉じカッコと半角アンダーバーの間に半角スラッシュを入れないとmarkdownからhtmlへの翻訳の仕様でバグるらしい。

数式環境をくくる大括弧と数式環境内の中括弧や半角空白や濃度のシャープは半角スラッシュ２つ、改行は半角スラッシュ５つ、その他は基本的に半角スラッシュ１つで良さそう。htmlとmathjaxの関係が難しい。

inline数式内の縦棒はlvertなどを使わないとmarkdownの表と認識される。

arrayとalignはどちらも使える。arrayが使えない気がしてしまったのは中括弧につける半角スラッシュの個数を間違えていたから。alignはアンパサンドを等号の右側につけて半角空白を２つ入れると幅がちょうど良さそう。arrayなしだとアンパサンドは使えない。