Quiz
- npca2015年部誌_木に対する一般的なテク達.pdf p36
- Running Away from the Barn (USACO 2012 December Gold)
木上の点に一律の値を足す
- これをO(logN)でする方法が必要
- 下図のようなグラフを考える
- オイラーツアーとBITを使う
- vの先祖がuである場合のみ使える方法です (2021/08/07追記)
- u, v (depth[u] < depth[v])とする
- BITのleft[u]に+1, left[v]+1に-1する（ここでいうleftとはオイラーツアーの左端)
- uの値を求める時はBIT.sum(left[u]) - BIT.sum(right[u])
- 実際に求めてみると下図のようになり、求まっている
学んだこと
木上の点に一律の値を足す方法
【要検証】先祖関係でない場合
- LCAを求めて足し引きすればよさそう
- TODO：何らかの問題でverify
