Entries from 2018-01-20 to 1 day

根が頻繁に変わる木で親を求める

根が のとき頂点 の親を で求めるコード。以下の場合分けによるアルゴリズム。 $r$ が $u$ の子孫だった場合、$r$ を $u$ にぶつからない限界まで持ち上げる。 それ以外の場合、根が頂点 0 だった場合の親をそのまま返す。 // Verified at http://codeforces…

根が頻繁に変わる木でLCAを求める

根が $r$ のときの頂点 の LCA を とする。 のうち最も頂点 から遠い頂点が である。この機能を持ったHL分解のライブラリを書いておく。きちんとした証明はしてないけど多分問題ない。 // Verified at http://codeforces.com/problemset/problem/916/E struc…

CF #457 E. Jamie and Tree

http://codeforces.com/problemset/problem/916/ELC-tree は根を変更するクエリと lca を求めるクエリを捌ける。ET-tree は辺の追加・削除と連結成分全体に x を一様加算するというクエリが捌ける。これらを組み合わせることで容易に解くことができる。 #inc…

CF #457 D. Jamie and To-do List

http://codeforces.com/problemset/problem/916/D誤読さえしなければ解法は自明。永続multiset と永続配列があれば良い。永続multisetは使いまわせそうな形で再実装した。内部的には LLRBtree を用いている。 ポインタ型が64bitというのが厄介で、nodeにポイ…