题目列表

子树重心必在重儿子的重心到根的祖先路径上；可自底向上继承重儿子的重心并向上跳，均摊 O(n+q)；也可用倍增跳表沿重链向下跳，每次查询 O(log n)，后者可迁移到删边类问题。

加虚拟源点把「建电站」变成一条边，答案成为 n+1 个点的最小生成树；稠密完全图上选 O(n²) 的 Prim 现场扫描，不落地保存两百万条边。

把子树加值改写成差分数组上的两次点修改，购买集合可行等价于对应边让 0..m 连通，于是第一问变成最小生成树；第二问用按权值分组的 Kruskal 判定每条边是否属于某棵 MST。

外层线段树按 x 组存区间最大 y，靠「整段最大值不够就剪掉」单路下降定位最左可行 x；组内可用 std::set 或离线压缩后的 Fenwick 维护。

折半枚举每个数的不选、原值、阶乘三种状态，按使用贴纸数统计目标和方案。

把质数拆成两组生成所有乘积，二分答案并双指针统计不超过它的乘积对数。

枚举三个字符串的拼接顺序，用 KMP 求相邻字符串的最大后缀前缀重叠。

最后一步必含首或尾；Alice 胜当且仅当 a1=1 或 an=1。