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

pekempeyのブログ

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

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

LCA

単に面倒なだけ。 codeforces.com 解法 a と b の LCA が a または b のとき、赤色の頂点とオレンジ色の頂点を結ぶ辺を追加すると a, b がサイクルに含まれる。 そうでないとき、赤色の頂点とオレンジ色の頂点を結ぶ辺を追加すると a, b がサイクルに含まれ…

Educational Codeforces Round 3 E. Minimum spanning tree for each edge

ダブリング練習用の問題。HL 分解でもいける。 問題文 http://codeforces.com/contest/609/problem/E 問題概要 重み付き無向グラフが与えられるので、i 番目の辺を使った最小全域木の重みを、すべての i に対して求めよという問題。 最大の頂点数は 2・105、…