pekempeyのブログ

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

HL-Decomposition

NJPC2017 H - 白黒ツリー

想定解よりは複雑だけど、HL分解の方が応用が効くので書いておきます。H: 白黒ツリー - NJPC2017 | AtCoder

AOJ 2450 Do use segment tree (HL Decomposition)

LC木解は以前書いたのですが、HL 分解の方もコードだけ置いておきます。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2450

Dynamic connectivity contest: Bridges in a Tree

問題ページ 問題概要 木が与えられる。初期状態に辺 e1, e2 ,..., eK を加えたとき橋はいくつあるかという M 個のクエリを順次処理せよ。 2≦N≦100,000 1≦M≦100,000 ΣK≦100,000

Codeforces Round #359 (Div. 1) B. Kay and Snowflake

http://codeforces.com/contest/685/problem/B 問題 木が与えられる。頂点 v[i] を根とする部分木の重心を求めるクエリを Q 個処理せよ。 2≦n≦300,000 1≦q≦300,000

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

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

HL分解 (Heavy-Light Decomposition)

HL分解で解ける問題を最近よく見る。(想定解法であるかどうかは別として)No.235 めぐるはめぐる (5) - yukicoder F: 根付き木のみさわさん - 天下一プログラマーコンテスト2015本戦(オープンコンテスト) | AtCoder Problem - 588E - Codeforces Problem …

Codeforces Round #329 (Div. 2) D. Happy Tree Party

問題 codeforces.com