今回扱うのはyukicoder contest 368 F問題 No.2129 Perfect Binary Tree…?です。公式解説の補足として、考察の楽をするテクニックを解説します。

問題の概要

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

$2^N - 1$頂点の無向完全二分木に無向辺$u \leftrightarrow v$を$1$本追加したグラフを$G$と置く。$G$の各$2$頂点の距離の総和をmod $998244353$で求めよ。

前置き

$u,v$が最初から隣接している場合や$u = v$である場合は、$G$が無向完全二分木そのものです。無向完全二分木に対する答えは再帰的な定義を紐解くことで明示式でも求められそうですが、木DPを用いることで考察せずとも$O(N)$で求められます。

今回はそういった楽の仕方を一般の場合に拡張しようというお話です。

解説

$G$が無向完全二分木そのものではない場合、つまり閉路を持つ場合を考えます。

この時$G$はなもり先生グラフとなるので、閉路の周りに無向木がくっついているグラフとなります。閉路とくっついている頂点を根とすることで、無向木を根付き木とみなします。

各根付き木$T$の

• 頂点数$V(T)$
• 根から各頂点の距離の総和$D(T)$
• 各$2$頂点の距離の総和$W(T)$

をmod $998244353$で求めることができれば、答えは単純な内積などの和になり畳み込みで計算することができます。

公式解説ではこれらを$A,B,C$と置いて具体的に求めていますが、木$T$の各$2$頂点の距離の総和は木DPで$\Theta(V(T))$で求めることが可能です。

とはいえ木DPを$\Theta(V(T))$で処理すると合計で$\Theta(2^N)$の時間がかかってしまいます。

ここで、もし$T$が無向完全二分木であれば同型な木に対する処理を省略することで$O(\log_2 V(T))$で木DPを処理することができます。

$T$がほとんど無向完全二分木であること、より正確には$T$は無向完全二分木から部分木を$1$点に潰したものとなっていることに注意すると、$T$に対する木DPを行わずとも無向完全二文木に対してのみ木DPを行えば良いです。

何故でしょうか？　そもそも一般の根付き木$T$に対して$W(T)$を木DPで求めるには、組$(V(T),D(T),W(T))$に対して根付き木の結合と整合的なモノイド演算を定めれば良いです。

具体的には、根付き木$T,T’$の根を結合して得られる根付き木を$T+T’$と置くと

• $V(T+T’) = V(T) + V(T’) - 1$
• $D(T+T’) = D(T) + D(T’)$
• $W(T+T’) = W(T) + D(T) \times (V(T’) - 1) + (V(T) - 1) \times D(T’) + W(T’)$

となることに注目して

\[ (v,d,w) \oplus (v’,d’,w’) = (v+v’-1,d+d’,w+d(v’-1)+(v-1)d’+w’) \]

という演算$\oplus \colon \mathbb{Z}^3 \times \mathbb{Z}^3 \to \mathbb{Z}^3$を定めれば良いです。定義から即座に

\[ (V(T),D(T),W(T)) \oplus (V(T’),D(T’),W(T’)) = (V(T+T’),D(T+T’),W(T+T’)) \]

となり、$T \mapsto (V(T),D(T),W(T))$という対応が$+,\oplus$について準同型性を持つことが分かります。

そして根付き木の根に無向辺を$1$本接続して根をもう一端に移動させる処理は

\[ \textrm{Extend} \colon (v,d,w) \mapsto (v+1,d+v,w+d+v) \]

という演算$\textrm{Extend} \colon \mathbb{Z}^3 \to \mathbb{Z}^3$に翻訳でき、$\oplus$と$\textrm{Extend}$を組み合わせることで木DPを容易に処理できます。

特に、閉路のうち$u,v$のLCAでない頂点にくっついている根付き木$T$に対する$(V(T),D(T),W(T))$は無向完全二分木$T’$に対する$(V(T’),D(T’),W(T’))$を前計算しておくことで$\Theta(\log_2 V(T))$で計算できます。

さて、重要なのは$\oplus$が実は可換群演算であることです。つまり根付き木の結合のみならず、根付き木の根から辺を$1$本選んで根と反対側の頂点を根とする部分木を削除する操作も$\oplus$に関する逆元を用いて翻訳できます。これにより$u,v$のLCAにくっついている根付き木$T$に対する$(V(T),D(T),W(T))$も$\Theta(\log_2 V(T))$で計算できます。

以上で、$G$の閉路の周りにくっついている各根付き木$T$（木としては、無向完全二分木から部分木を$1$点に潰したもの）に対する$(V(T),D(T),W(T))$を合計$O(N)$で計算できました。

この解法は、細かい考察や計算が不要で可換群のインタフェースを整えるだけで実装でき、しかも$\oplus$は一般の根付き木に使えるため他の問題にも流用させられるので、ライブラリを充実させて考察や実装のミスを減らしたい人におすすめです。

実装例

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

自分用覚え書き

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

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

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

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