euler, tour, tree の検索結果:

Educational Codeforces Round 71 (Rated for Div. 2) G. Indie Album

…lue using Euler tour. Both the time and the space complexity is linear logarithmic. When the space complexity is linear logarithmic, we often violates the memory limit. Maybe, lazy propagation segment tree will over the limit. \documentclas…

CF #457 E. Jamie and Tree

…}; struct EulerTour { std::vector<int> l; std::vector<int> r; EulerTour(const std::vector<std::vector<int>> &g) { const int n = g.size(); l.resize(n); r.resize(n); int k = 0; std::function<void(int, int)> dfs = [&](int u, int p) { l[u] = k+…

Sandy the foodie

https://www.codechef.com/problems/KOK100euler-tour tree。O(n log n) ではあるけど、定数倍が重くて通らなかった。euler-tour を考えるとき辺で見るか、頂点で見るかどちらかだと思うけど、辺で考えると対称性が良い気がするので辺で実装している。今回の問題のように頂点に値を持たせる場合は、仮想的な何かを差し込んでおいてそれを使うと良い。

101 Hack May 2016: Tree Splitting (euler-tour tree 解)

…すかもしれません。 Euler-tour tree Euler-tour tree は以下の操作が行える動的木。 link(u,v) := u,v を辺で繋ぐ。 cut(u,v) := u,v を繋ぐ辺を削除する。 操作を拡張すれば、 is-connected(u,v) := u,v が同じ連結成分に属するか判定する。 size(u) := u が属する連結成分のサイズを計算する。 などの操作も可能。連結成分に強いのかな。ただし木限定。 次のような木があったとする。 この木を…

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

…解法を考えてみた。 euler tour を用いた解法はこちら。 pekempey.hatenablog.com 解法 link-cut tree のノードに次の情報を追加する。 solid-edge で繋がれた頂点の部分木のサイズ dashed-edge で繋がれた頂点の部分木のサイズ dashed と solid が変わりそうなのは expose, link, cut の 3 つである。solid,dashed が入れ替わるタイミングで dashed-sub も一緒に更新…

HackerRank 101 Hack May 2016: Tree Splitting

…r部 に書いてある euler tour tree と同じものだと思うけどどうなんだろう。 (追記:2016/06/25)本物の euler tour tree は全然違うものでした。 問題 n 頂点の木が与えられる。頂点 v と連結している要素数を答え、v を削除するというクエリを m 回処理せよ。 オンラインクエリ 解法 辺の削除を実現すればいい。 euler tour と二分探索木を使うことで、v の部分木を切り離すという操作が O(log n) で可能になるのでこれを…

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

…Cはできた)LCA+eulertourも行ける気がする。(ただ0の逆元の対処が可能かは知らない) こんな感じにルート間クエリが計算できる。 一番最初からぐにょーと掛ければ大体打ち消して欲しい値が残る。 #include <bits/stdc++.h> #define GET_MACRO(a, b, c, NAME, ...) NAME #define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__) #defin…