PCK2017 予選11 ネットワークの課金システム - てんぷらのぷらはC++のぷら

自分のブログの存在を完全に忘れていた(おいおい)。問題を解きました。

Charging System for Network | Aizu Online Judge

問題概要

頂点数Nの木(各辺s-t はコストc[s,t]を持つ)と整数Kが与えられる。以下のクエリをQ回処理する。

send : 2頂点u-v間のパスのコストの総和を答える。ただしコストがKの倍数である辺は0として計算する。
add : 頂点uから伸びているすべての辺のコストをd増やす。

制約は 1<=N,K,Q<=10^5

解法

明らかに「Kの倍数は0とする」の部分が厄介です。

addクエリは頂点に足された値を記録しておけば(これをa[u]などと書きます)辺u-vのコストは c[u,v]+a[u]+a[v] と計算できるが、sendクエリで普通に辺を1つずつ見ていくとO(N)かかってしまってダメ。

「Kの倍数は0とする」の操作をaddに押し付けることができればsendはオイラーツアーなりなんなりで高速に答えられるようになるけど、今度はaddで頂点の周りの辺をすべて見ないといけないのでO(N)かかってしまう。

八方塞がりに思えるのですが、ここでHL分解の以下の性質を思い出します。

(HL分解そのものについては書かないです、ごめんなさい(僕はこの方の記事で勉強しましたHeavy-Light Decomposition - beet's soil))

各頂点についてそこから出るHeavy edgeは高々2本
各パスについて、通るLight EdgeはO(logN)本

するとこのような折衷案が思いつきます。

addクエリでは、頂点に足された値を記録した後、Heavy Edgeの値を更新する。
sendクエリでは、Heavy Edge は更新されているのでそのまま利用して、Light edge については1つずつ計算する。

上記の性質により、addクエリでは2箇所、sendクエリではO(logN)箇所しか計算をしないので高速に行うことができます。求めたいものは区間和なのでセグメントツリーを用いることで、addクエリをO(logN)、sendクエリをO((logN)^2)で処理でき、全体計算量は最初の入力等も含めてO(NlogN+Q(logN)^2)となり無事解くことができました。

実装↓ (雑然としているのでアです)

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3100945