Codeforces Round #342 (Div. 2) E. Famil Door and Roads
単に面倒なだけ。
解法
a と b の LCA が a または b のとき、赤色の頂点とオレンジ色の頂点を結ぶ辺を追加すると a, b がサイクルに含まれる。
そうでないとき、赤色の頂点とオレンジ色の頂点を結ぶ辺を追加すると a, b がサイクルに含まれる。
したがって以下の 3 つの情報があれば期待値を計算できる。これらは 2 回 DFS すれば求まる。
- 部分木のノード数
- v から部分木の各頂点への距離の総和
- v から他の頂点への距離の総和
計算式を立てる作業は地道なので、他人のコードを見るか自分で考えたほうが早いと思う。よって省略。
Codeforces Round #342 (Div. 2) E. Famil Door and R ...
時間内に通すことができず残念。