pekempeyのブログ

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

Link-Cut Tree

Week of Code 27: How Many Substrings?

どうせ平方分割だろうと思って editorial を覗いてみたら、想像以上に解法が面白かった。editorial を読んでもよく分からなかったので、簡単に解法に至る流れを書き留めておく。 間違ったこと書いていたらごめんなさい。 https://www.hackerrank.com/contest…

Dynamic connectivity contest: GraphAero

問題ページ とりあえず LC 木で解けるので解きました。ただこの方法だと D 問題が解けない。 問題概要 N 頂点 M 辺の無向グラフが与えられる。辺(u,v) を追加するというクエリが K 個与えられるので順次処理せよ。各クエリを処理した後、グラフ中にある橋の…

101 Hack May 2016: Tree Splitting (link-cut tree 解)

https://www.hackerrank.com/contests/101hack37/challenges/tree-splitting link-cut tree で解けるということは知っていたので、link-cut tree で解法を考えてみた。 euler tour を用いた解法はこちら。 pekempey.hatenablog.com

AOJ 2450 Do use segment tree

LC木の理解が浅かったため、図が微妙に間違っています。気をつけてください。 HL 分解+遅延 segment tree でも解けるが、ここでは link-cut tree で解く。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2450 問題 木と Q 個のクエリが与えられ…