この問題はグラフに帰着して解くことができます。以後、グラフ理論の言葉を使います。

1. 最初の問題

まず、適切な向き付けをすることで強連結成分にできる部分は明らかに強連結成分にすべきです。この「適切な向き付けをすることで強連結成分にできる部分」は「二重辺連結成分」と同値であることが分かります。二重辺連結成分分解はグラフを橋で区切ることで行えるため、 LowLink を使い \(O(N+M)\) で可能です。

さて、二重辺連結成分分解をすることで、この問題は次のような問題に帰着できます。

\(N'\) 頂点の木が与えられます。 各頂点には重みが付いていて、頂点 \(v\) の重みは \(W_v\) です。 辺に向き付けをして、次のように定義されるスコアを最大化してください。

スコア : 頂点 \(u\) から頂点 \(v\) に \(0\) 本以上の辺を使って移動できるような頂点の組 \((u,v)\) 全てに対する \(W_u \times W_v\) の総和

これは、元のグラフでの橋に向きを付け、二重辺連結成分をまたぐ頂点同士のGoTo度への寄与を最大化する部分問題です。

2. 部分問題1

さて、実はこの問題は次のように向き付けすると最適であることが証明できます(証明は後述)。

1. 重心 \(g\) を求める。ただし、ここでの重心とは、重心を取り除いたときに連結である成分(重心に対する無中心連結成分と呼ぶことにする)それぞれにおいて、成分内の重みの和が、重心を含めたグラフ全体の重みの和(\(=N\))の半分以下であるような頂点だとする。
2. 同じ無中心連結成分内の辺は、全て \(g\) から遠ざかる辺であるか、全て \(g\) に近づく辺であるかのどちらかである。

重心 \(g\) は重みなしの場合と同様に \(O(N')\) で計算でき、 \(g\) と他の頂点でのスコアへの寄与や、同じ無中心連結成分内の頂点同士でのスコアの寄与は簡単な \(O(N')\) の木DPで求めることができます。

3. 部分問題2

部分問題1で求めることができていないスコアは、無中心連結成分をまたぐ頂点同士についてのものです。 これは次のような部分問題に帰着できます。

要素数 \(K\) の集合 \(X\) が与えられます。 それぞれの要素を集合 \(Y, Z\) のどちらかに入れて、 \(\displaystyle \sum_{i \in Y} i \times \sum_{i \in Z} i\) を最大化してください。

ここで \(Y\) は \(g\) から遠ざかる辺を持つ無中心連結成分、 \(Z\) は \(g\) に近づく辺を持つ無中心連結成分を表します。

\(\displaystyle \sum_{i \in Y} i\) の候補はたかだか \(N+1\) 通りなので、候補を効率よく列挙することができれば \(O(N)\) で部分問題を解くことができます。

部分問題2 解法1 (bitset解)

次のような DP を考えます。

\(\mathrm{dp}[i][j]\) \(:=\) \(X\) の要素を \(i\) 個目まで使って総和を \(j\) にできるか

このままでは \(O(NK)\) の計算量がかかり間に合いませんが、この DP は bitset で高速化することができます。計算量は \(O \left (\frac{NK}{\mathrm{wordsize}} \right)\) となります。

部分問題2 解法2 (畳み込み解)

\(\displaystyle \prod_{i \in X} (x^i+1)\) の \(x^n\) の係数が \(0\) であるか否かで、 \(\displaystyle \sum_{i \in Y} i = Y\) とできるかが判定できます。平衡二分木を作るように畳み込みをすると計算量 \(O(N \log N \log K)\)で解くことができます。

以上より、全体で計算量 \(O\left(\frac{N^2}{\mathrm{wordsize}}\right)\) または \(O(N \log^2 N)\) でこの問題を解くことができました。

4. 証明

部分問題1の証明をします。

ある頂点 \(v\) に対する各無中心連結成分内の辺は、全て \(v\) から遠ざかる辺であるか、全て \(v\) に近づく辺であるかのどちらかであるような向き付けを、頂点 \(v\) を中心とする良い向き付けと定義します。

また、頂点 \(v\) を中心とする良い向き付けの中で、最もスコアが高くなる向き付けを最良の向き付けと定義します。

4-1. パート1

向き付け後のグラフにおいて、次の条件を満たす頂点の組 \((u, v)\) を重要な頂点の組と呼ぶことにします。

• 頂点 \(u\) から頂点 \(v\) に \(1\) 本以上の辺を使い移動することができる
• 頂点 \(u\) の出次数が \(2\) 以上である
• 頂点 \(v\) の入次数が \(2\) 以上である

実は重要な頂点の組を持つ向き付けには、スコアが真に改善される別の向き付けが存在することが次のように証明できます。

A   F   C
↑   ↑   ↑
u → E → v
↑   ↑   ↑
B   G   D

さて、重要な頂点の組が存在しないことは、ある頂点を中心とする良い向き付けであるということと同値であることが簡単に分かります。

先ほど証明した事実と組み合わせると、最もスコアが高い向き付けは、ある頂点を中心とする良い向き付けであるということが証明できました。

4-2. パート2

次に、重心 \(g\) を中心とする良い向き付けが最もスコアが高くなることを証明します。

パート1で証明した事実より、任意の頂点 \(u\) について、 \((\) 頂点 \(u\) を中心とする最良の向き付け \()\) \(\leq\) \((\) 重心 \(g\) を中心とする最良の向き付け \()\) を示せばいいです。

次の図のような状態を考えます。

A   B   C   D
|   |   |   |
u - v - w - g

この図で \(A\) から \(D\) までの記号は次の頂点の集合を表します。

• \(A\) : 頂点 \(u\) を取り除いたとき、頂点 \(v\) と非連結になる頂点。
• \(B\) : 頂点 \(v\) を取り除いたとき、頂点 \(u, w\) と非連結になる頂点。
• \(C\) : 頂点\(w\) を取り除いたとき、頂点 \(v, g\) と非連結になる頂点。
• \(D\) : 頂点 \(g\) を取り除いたとき、頂点 \(w\) と非連結になる頂点。

このグラフを頂点 \(u\) に対する最良の向き付けにすると、 \(g\) が含まれる無中心連結成分に全体の半分以上の重みがあることより、次のようになります。

A   B   C   D
↓   ↑   ↑   ↑
u → v → w → g

これはよく見ると、頂点 \(v\) に対しても良い向き付けであることが分かります。よって、 \((\)頂点 \(u\) に対する最良の向き付けのスコア\()\) \(\leq\) \((\)頂点 \(v\) に対する最良の向き付けのスコア\()\) となります。

さらに頂点 \(v\) に対する最良の向き付けは以下のようになります。

A   B   C   D
↓   ↓   ↑   ↑
u → v → w → g

同様の議論より、 \((\)頂点 \(u\) に対する最良の向き付けのスコア\()\) \(\leq\) \((\)頂点 \(w\) に対する最良の向き付けのスコア\()\) となります。

そして頂点 \(w\) に対する最良の向き付けは以下のようになります。

A   B   C   D
↓   ↓   ↓   ↑
u → v → w → g

同様の議論より、\((\)頂点 \(u\) に対する最良の向き付けのスコア\()\) \(\leq\) \((\)頂点 \(g\) に対する最良の向き付けのスコア\()\) という結論を得ることができました。

頂点 \(u\) と頂点 \(g\) の間にいくつの頂点があっても同様の議論が成り立つため、任意の頂点 \(u\) に対して、 \((\)頂点 \(u\) に対する最良の向き付けのスコア\()\) \(\leq\) \((\)頂点 \(g\) に対する最良の向き付けのスコア\()\) が成り立つことが証明できました。

以上より、パート1と合わせて、重心を中心とする最良の形が最もスコアが高いことを証明できました。

5. 重心が \(2\) つある場合

今までの議論は重心が \(1\) つであることを前提にしていました。しかし、実際には重心は \(2\) つの場合もあるということが知られています。その場合はどうなるのでしょうか。

実は、どちらの重心でも最良の向き付けは変わらないことが簡単に分かります。 図にするとこのような感じになります。

A → g1 → g2 → B

詳しくは説明しませんが、どちらの重心でもこれが最良の形になります。

6. 別解

実は、 4. の証明のパート1のみを使った解法が存在します。 重心ではない頂点 \(u\) を中心に最良の向き付けを作るとき、「重心を含む無中心連結成分」を \(u\) から遠ざかる辺、「それ以外の無中心連結成分」を \(u\) に近づく辺にした向き付けが最良の向き付けになっています。そのため、前計算で \(O(N')\) の全方位木DPを使うことで、重心ではない頂点 \(u\) について最良の向き付けのスコアを \(O(\deg(u))\) で求めることができます。よって全体の計算量は、 \(\displaystyle\sum_{u \in V} \deg(u)=2(N'-1)\) より、 \(O(N+N \log^2 N)\) などになります。

7. 実装例

bitset解 (C++, 358ms)

畳み込み解 (C++, 192ms)

別解 (畳み込み解) (C++, 245ms)