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

Lovely_yhb · 2025-02-13 14:28:40 · 个人记录

因为没有包含，所以左端点靠右的右端点一定靠右。把环断开，复制一份在后面，问题是选多少个区间能覆盖 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 跑两遍就是了。