実は解候補はlca(A,B), lca(B,C), lca(C, A)の3通りしかない。 与えられた木を根付き木とし、簡単のため depth(A) <= depth(B) <= depth(C) とする。Aを考慮しなければ、下のような図が描ける。 (1)Aがパス(B,C)上にある場合 明らかにAが解になる。 A=lca(A,…

文字列a,ab,abc,abdが与えられているとする。上図のようなtrieを描いてみよう。 簡単のため、文字列の最大の長さは考えないでみる。 K=1とすると明らかにaだけを使えばいい。 では、K=2の場合は？ K=1のときと同じようにaを使おうとすると、うまくいかない。…

更新の操作は以下のように表せる。 A[i]+=s A[j]+=-s/(N-1), j!=i 前者を変形すれば A[i]+= (s+s/(N-1)) -s/(N-1) となる。なので 全体に-s/(N-1)を加算し、A[i]にs+s/(N-1)を加算したとすれば、1クエリO(1)で処理できる。