読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #342 (Div. 2) E. Famil Door and Roads

単に面倒なだけ。

codeforces.com

解法

a と b の LCA が a または b のとき、赤色の頂点とオレンジ色の頂点を結ぶ辺を追加すると a, b がサイクルに含まれる。

f:id:pekempey:20160221215706p:plain:w250

そうでないとき、赤色の頂点とオレンジ色の頂点を結ぶ辺を追加すると a, b がサイクルに含まれる。

f:id:pekempey:20160221215847p:plain:w250

したがって以下の 3 つの情報があれば期待値を計算できる。これらは 2 回 DFS すれば求まる。

  • 部分木のノード数
  • v から部分木の各頂点への距離の総和
  • v から他の頂点への距離の総和

計算式を立てる作業は地道なので、他人のコードを見るか自分で考えたほうが早いと思う。よって省略。

Codeforces Round #342 (Div. 2) E. Famil Door and R ...

時間内に通すことができず残念。