高度由习惯堆积

分类 数据结构:倍增 下的文章

NOIP2018 保卫王国

题目Z 国有 $n$ 座城市,$n−1$条双向道路,每条双向道路连接两座城市,且任意两座城市都能通过若干条道路相互到达。Z 国的国防部长小 Z 要在城市中驻扎军队。驻扎军队需要满足如下几个条件:一座城市可以驻扎一支军队,也可以不驻扎军队。由道路直接连接的两座城市中至少要有一座城市驻扎军队。在城市里驻扎军队会产生花费,在编号为 $i$ 的城市中驻扎军队的花费是 $p_i$。小 Z 很快就规划出...

CF587C Duff in the Army(树上倍增 树链剖分)

题目有n个城市,由n-1条边连接。两个城市之间的道路是唯一的。 有m个人,住在这n个城市中,现在给出m个人,生活的城市编号。 你需要回答,从一个城市u到另一个城市v的路径中,编号前a小的人的编号是哪些?思路1(树上倍增)树上倍增,可以开一个$num[i][j]$,表示i这个点向前跳$2^j-1$格后到达的点,这样,对于两个点而言,就可以向上跳跃,直到交汇为止,答案则是归并后的ans数组。此题...