PCK2017K (予選) - ネットワークの課金システム

問題文

Aizu Online Judge

解法

クエリを$${B}$$個ごとにまとめて処理することを考えます。

加算クエリは、頂点の重みを増やすことで高速化を図ります。これにより、辺$${i}$$の重みが$${w_{a_i} + w_{b_i} + c_i}$$で計算できます（$${w_v}$$は頂点$${v}$$の重み）。

また、加算クエリで現れる$${x}$$からなる集合$${X}$$を求めます。$${X}$$に属している、または$${X}$$に属している頂点と隣接している頂点を悪い頂点と呼ぶことにします。逆に、これ以外の頂点を良い頂点と呼びます。重要な事実として、どのパスも悪い頂点を高々$${3B}$$個しか含みません。

パスクエリは、木を適当な根付き木と見做して処理します。$${\mathrm{lca}(s, t) = t}$$のケースが分かればよいです。悪い頂点に辺が接続しているときは愚直に処理します。良い頂点が連続している所は適当に圧縮します（辺の重みが変わらないので、まとめて計算したいという気持ち）。どちらも「次に行く頂点」と「移動コスト」の 2 つが分かるようにしておけばよいです。この 2 つは DFS で前計算します。$${t}$$に至る過程で頂点の移動は高々$${6B}$$回行います。よって、LCA の計算と合わせて、パスクエリは$${O(B+\log N)}$$時間で処理できます。

全体での計算量を考えると、

• 加算クエリ:$${O(1)\times O(Q) = O(Q)}$$

• 悪い頂点の列挙:$${O(N)\times O(Q/B) = O(NQ/B)}$$

• 「次に行く頂点」と「移動コスト」の計算:$${O(N)\times O(Q/B) = O(NQ/B)}$$

• パスクエリ:$${O(B+\log N)\times O(Q) = O(Q(B +\log N))}$$

なので$${B = O(\sqrt{N})}$$とかにすると TLE せずに通ると思います。

提出コード

Aizu Online Judge