CSP-S 2024 第八次

忘记写了，补一下

A

依次加入每个 \(a_i\)，拿个大根堆维护当前以 \(i\) 结尾的和最大子段，和超过 \(s\) 了就弹堆顶直到和不超过 \(s\)。

不过好像出现了一些语文事故，先不管了。

B

倍增预处理出 \(f_i\) 表示 \(i\) 上方第一个大于 \(a_i\) 的点，

询问 \(u,v,c\) 时，先倍增找到 \(u\) 上方第一个大于 \(c\) 的点 \(x\)，然后就要求跳（\(x\gets f_x\)）几次能跳出 \(v\)，在 \(f\) 上倍增即可。

C

最大值最小，先二分。

设 \(f_{u,x,y}\) 表示是否存在走完 \(u\) 子树，\(u\) 到第一个叶子的距离为 \(x\)，最后一个叶子到 \(u\) 的距离为 \(y\) 的方案，

可以发现 \(x\le x',y\le y',f_{u,x,y}=1\) 时我们就不关心 \(f_{u,x',y'}\) 了，所以我们关心的 \(f_{u,x,y}\) 只有 \(O(s_u)\) 个（\(s_u\) 是 \(u\) 的叶子个数）

考虑转移，双指针合并左右子树的状态，然后只留下我们关心的状态即可。

D

【模板】最小斯坦纳树

设 \(f_{u,S}\) 表示以 \(u\) 为根的树覆盖 \(S\) 中的点的最小代价，考虑转移：

• 不改变根，可以合并已有的两棵树，即 \(f_{u,S}+f_{u,T}\to f_{u,S\cup T}\)。
• 改变根，可以在根上连接一条边，即 \(f_{u,S}+e(u,v)\to f_{v,S}\)，其中 \(e(u,v)\) 是 \(u,v\) 之间的边权。

第一种转移直接枚举子集做，第二种转移类似 Dijkstra 地做即可。