Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


  1. 「SCOI2005」王室联邦 - 树分块

    他想把他的国家划分成若干个省,每个省都由他们王室联邦的一个成员来管理。他的国家有 n n 个城市,编号为 1n 1 \ldots n 。一些城市之间有道路相连,任意两个不同的城市之间有且仅有一条直接或间接的道路。

    每个省至少要有 B B 个城市,最多只有 3B 3B 个城市。

    每个省必须有一个省会,这个省会可以位于省内,也可以在该省外。但是该省的任意一个城市到达省会所经过的道路上的城市(除了最后一个城市,即该省省会)都必须属于该省。

    一个城市可以作为多个省的省会。

    于  BZOJ, SCOI, 分块, 数据结构, 树分块 继续阅读