オイラーツアー

Range Query on a Tree ~木上の1点加算、根までの和~

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_D&lang=ja AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4879659#1 解説 辺に足すという操作は、葉側の頂点に足すと言い換えてOK get sumクエリが来たときは、指定された…

木上の点に一律の値を足す & 各点の現在値を求める

Quiz npca2015年部誌_木に対する一般的なテク達.pdf p36 Running Away from the Barn (USACO 2012 December Gold) 木上の点に一律の値を足す これをO(logN)でする方法が必要 下図のようなグラフを考える オイラーツアーとBITを使う u, v (depth[u] < depth[v…

C - On Changing Tree ~オイラーツアーとセグ木~

Quiz https://codeforces.com/contest/396/problem/C N頂点の木 (3 x 10^5) クエリQ (3 x 10^5) ・1 v x k : 頂点vにxを足す。vの子孫にも、vからの距離 i によりx - i kを足す ・2 v : 頂点vの値をmod 10^9+7でprint 足す値が一律ではないことをどう扱うか …

オイラーツアーと、木のdfs --No.778 クリスマスツリー--

Quiz https://yukicoder.me/problems/no/778 AC Code (BIT ver) https://yukicoder.me/submissions/353994 AC Code (Euler Tour ver) https://yukicoder.me/submissions/354000 はじめに https://betrue12.hateblo.jp/entry/2019/06/22/195307 こちらを読め…