题意一棵 $n(\le 50000)$ 个点的树，有 $m(\le 50000)$ 支军队驻守在一些节点。要求根节点到每个叶子节点之间的路径上都有军队驻守，军队可以同时移动，每小时移动 $1$ 单位长度。问至少要多久才能满足条件，无解输出 -1（没有）。题解答案显然满足单调性，所以可以二分答案 $mid$ 。接下来只需要判断在 $mid$ 时间内能否满足条件。(1)如果军队 $i$ 在根节点...
题意环上有 $m(\le 10^9)$ 个点，有 $n(\le 2\times 10^5)$ 个人可以从 $l_i\rightarrow r_i$ 。对于所有的 $i\in [1,n]$ ，询问如果第 $i$ 个人必须选且为起点，至少要选多少人才能绕完一圈。题解首先断环成链。容易想到贪心，每次选 $l_i\le $ 当前的 $r$ ，$r_i$ 最大的 $i$ 作为下一步。一步一步跳是 $O...
题意有一棵 $N$ 点的树，有 $Q$ 次询问 $(a,b,c,d)$ ，问 $a\rightarrow b$ 与 $c\rightarrow d$ 是否相交。$N,Q\le 100000$ 。题解可以发现两条边相交，就一定存在一条边的最高点在另一条边上，即端点的 $\text{LCA}$ 。所以只用求 $\text{LCA}$ 就行了。第一次写倍增 $\text{LCA}$ ，感觉还是树剖...
题意要从一个 $N$ 点 $M$ 边的有向图的 $1\rightarrow N$ ，每秒可以走 $2^k$ 条边（$k$ 是任意自然数），求最少要花多少秒。$N\le 50 \ , \ M\le 10000$ 。题解用一个 bool 数组 $s[i][j][p]$ 表示能否走 $2^p$ 条边从 $i\rightarrow j$ ，可以通过倍增预处理出所有情况。这样就得到了所有能在 $1s$...