木上の点に一律の値を足す

Quiz

  • npca2015年部誌_木に対する一般的なテク達.pdf p36
  • Running Away from the Barn (USACO 2012 December Gold)

木上の点に一律の値を足す

  • これをO(logN)でする方法が必要
  • 下図のようなグラフを考える

f:id:peroon:20191123200813p:plain

  • オイラーツアーとBITを使う
  • u, v (depth[u] < depth[v])とする
  • BITのleft[u]に+1, left[v]+1に-1する(ここでいうleftとはオイラーツアーの左端)
  • uの値を求める時はBIT.sum(left[u]) - BIT.sum(right[u])
  • 実際に求めてみると下図のようになり、求まっている

f:id:peroon:20191123200915p:plain

学んだこと

木上の点に一律の値を足す方法