小課題1,2

各クエリについて、愚直にシミュレーションをして答えを求めます。具体的には、priority_queueを使うか、木dpをすることで求めることが可能です。

小課題3

愚直にシミュレーションを一回した後、累積和を用いて和の計算を高速化すると解くことができます。

小課題4

ある氷の大きさの変化を考えると、傾きが \(0,-1,0\) と変化する折れ線グラフになっています。このグラフ \(N\) 個の和のグラフについても、\(O(N)\) 個の線分に分割することが可能で、二分探索を適切に用いて各時刻に対する答えを求めることができます。

小課題5

時刻の昇順に答えを求めることを考えます。

基本的な方針は、氷の状態を BIT で管理するというものです。一つの氷の大きさが、傾きが \(0,-1,0\) と変化する折れ線グラフになっていることを思い出します。傾きが \(0\) の部分については、単にその大きさを BIT で持てば良いです。傾きが -1 の部分については、線分を延長したときの \(y\) 切片の和と、傾きが \(-1\) になっている氷の数がわかれば良く、これもまた BIT で管理できます。結局のところ、BITを数本持つことでこの問題を解くことが出来ます。

別の方針としては、セグ木状に区間を用意し、それぞれの区間について、区間の氷の大きさの和を表す折れ線グラフを管理すれば良いです。クエリでは、区間を取得した後、それぞれの区間について氷の大きさの和を求めれば良く、二分探索を用いることで実現することができます。クエリあたりの計算量は \(O(\log^2N)\) になります。クエリを時間の順にソートすれば、傾きと取得クエリが単調なCHT の \(\log\) を落とす要領で、\(O((Q+N)\log N )\) の計算量を達成できます。

小課題6

シミュレーションを愚直にやった後、根からの大きさの和をもち、LCAを高速に求めることでこの問題を解くことができます。

小課題7,8

基本的な方針は小課題5と同じです。木を \(O(\log N)\) 個のパスに分解できれば良く、これはHLD(重軽分解) を使えばいいです。もしくは、オイラーツアーとLCAを高速に求める手法とBITを組み合わせることでも解くことが出来ます。

「別の方針」を利用することもできます。この場合、クエリあたりの計算量 \(O(\log^2N)\) の方の解法を自然に拡張すると、クエリあたりの計算量が \(O(\log^3N)\) になってしまい、おそらくTLには間に合いません。\(O((Q+N)\log N )\) の解法を拡張することで、\(O(Q \log^2 N + N \log N)\) でこの問題を解くことができます。