COCI2020 contest #1 (Virtual)
50 + 70 + 110 + 50 + 50 = 310
リンク
histogram
分割統治
累積 min は単調減少であることを利用すると、尺取 + CHT on Segtree などで解ける
力技
papricice
切る辺の一方が他方の祖先である場合とそうでない場合で分ける。
前者は、部分木の大きさを$ S(u)で表すと、$ S(u), S(v) - S(u), N - S(v)の差を小さくする問題になり、これは$ uを固定すると、$ S(v)が$ \frac{N + S(u)}{2}付近になるような高々$ 2通りを調べればよい。後者も同様である。
DFS をしながら、
祖先にある頂点の$ S(v)の集合$ A
祖先でなく、子孫でもない頂点の$ S(v)の集合$ B
を管理しなければならないが、これは
DFS で入る時に$ Aに$ S(u)を追加
DFS で出る時に$ Aから$ S(u)を取り除き、$ Bに$ S(u)を追加
とすればよい。（これで全てのペアが見れるのは、後者の場合の対称性による）
tenis
各選手について、最も強いグラウンド$ G(u)を計算しておく。
$ G(u) \neq G(v)なら勝者は一意である。$ G(u) = G(v)となるペアは$ O(N)組なので全探索すればよい。
tie-break の処理は頑張る（とても面倒）