競技前
特に準備はしませんでした。
競技
全体
†long queue† うーん。
1問目 (9点)
高い部分点については何もわかりませんでした。
$9$ 点分の部分点については $\sum_{k=1}^{N} k^2 = \frac{N(N+1)(2N+1)}{6}$ を書けばもらえました。
2問目 (100点)
最短距離を前計算すれば $O((N+Q)N \log N)$ 時間でできます。
適当にダブリングし、始点、経路、終点をそれぞれダブリング上二分探索で選ぶと $O((N+Q) \log N)$ 時間になって満点がとれました。
実装にてこずってかなり時間をかけた気がします。 3 割くらい long queue のせいだと思っています。
(5/27修正：計算量に $Q$ が考慮されていなかった)
3問目 (36点)
前 $2$ つの部分点はもはや別の問題なので個別にプログラムを書きます。簡単です。
木DPをすれば多項式時間で解けることが明らかです。
自然に書くと時間計算量 $O(N^2 \log N)$ なので、合計 36 点がとれました。
ここで時間が切れました。