腾飞计划寒假第一课——树上倍增 2025/2/2

因为没有包含，所以左端点靠右的右端点一定靠右。把环断开，复制一份在后面，问题是选多少个区间能覆盖 $i$ 到 $i+n$。每次选区间能覆盖到的左端点最靠右的。

维护一棵树，每次查询一个子树中深度为 $x$ 的点有多少个。

用 dfs 序搞一个数组下来，数组中 $a_i$ 的值表示 dfs 序为 $i$ 的点的深度。

转换成给你一个序列，求这个序列中等于 $x$ 的有多少个。

设 $x_i$ 是 $j$ 子树中的一点，$t$ 是 $i$ 开始走的时间，$dep$ 是深度。

设 $f_i=t_i+dep_{x_i}$。

查询有多少 $f_i=w_i+dep_j$。$w_i$ 是题目中给出的。

没听懂 qwq。

设 $f_{i,0/1}$ 表示 $i$ 的子树选完了，$i$ 选不选的答案。

整颗树的 dp 信息减去 $i$ 的 dp 信息得到剩下的 $g_{i,0/1}$ 表示 $i$ 子树外的最小代价。

如果 $x$ 和 $y$ 是祖先关系，每次询问答案是 $f_{x,a}+g_{y,b}+ans_i$，$ans_i$ 表示 $x$ 到 $y$ 的最小代价。

求 $ans_i$ 的方法：倍增数组 $F_{i,j,0/1,0/1}$ 表示从点 $i$ 跳 $2^j$ 步，起点和终点选或不选的方案。

如果 $x$ 和 $y$ 不是祖先关系找 LCA 跑两遍就是了。