2026.2.27
Hailiang 反讽（irony）
\(\color{blue}{贪心}\)
考虑把左括号看成 +1，右括号看成 -1。设 \(S\) 表示序列综合，\(L\) 表示前缀和的最小值。那么答案就是 \(S-2L\)。考虑最大化 \(L\)，那么在合并的时候，肯定希望“先走上坡，再走下坡”。考虑将一段连续的括号看作一个块。一个块总变化量，块最低点两个信息。容易根据这两个信息比较两个块。考虑将 \(A\) 序列分别分成若干段 \(A_1,A_2,\cdots,A_k\)，使得 \(A_1 \ge A_2 \ge \cdots, \ge A_k\)。容易使用单调栈分段。对 \(B\) 也分段，最后归并排序即可。
Hailiang 公交线路（bus）
\(\color{blue}{\text{DP}}\)
题目要求选择一个路径集合 \(S\)，使得这些路径构成的图 \(G\) 直径不超过 \(2\)。在树上，一组路径的交集非空是该组路径构成的图直径不超过 \(2\) 的充要条件。问题转化为：求有多少个路径子集，使得这些路径的节点交集非空。直接统计交集非空的集合比较困难，因为交集可能是一个点、一条边或一条路径。我们可以利用树上的容斥原理：\(\text{ans} = \sum_{u \in V} N(u) - \sum_{(u, v) \in E} N(u, v)\)
其中：\(N(u)\) 表示所有选定路径都经过点 \(u\) 的方案数，\(N(u, v)\) 表示所有选定路径都经过边 \((u, v)\) 的方案数。
假设我们固定点 \(u\) 为交集中的点。需要满足所有选中的路径必须经过 \(u\)，选中的路径的并集必须覆盖整棵树的所有节点。路径必须穿过 \(u\)，这意味着路径的一端在 \(u\) 的某个分支（或 \(u\) 自身）中，另一端在另一个分支中。选中的路径的并集必须覆盖整棵树的所有节点等价于：树上的每一个叶子节点，都必须是某条被选路径的端点。考虑使用容斥：枚举一个叶子节点的子集 \(A\) 表示叶子中没有被任何路径覆盖到的集合，计算方案数。$ N(u) = \sum_{A \subseteq \text{Leaves}} (-1)^{|A|} \times 2^{c(u, A)} $。其中 \(c(u, A)\) 是指经过 \(u\) 且两个端点都不在 \(A\) 中的路径数量。
可以用“总路径数”减去“各分支内部的路径数” 计算经过 \(u\) 的路径数。设 \(g_{u,i}\) 表示对于以 \(u\) 为根的子树，作为一个独立的分支连接到其父节点时，如果我们从中选定 \(i\) 个叶子不覆盖，该分支内部减少的路径贡献系数。\(g_{u,i} = (-1)^i \binom{L_u}{i} \times 2^{\binom{sz}{2} - \binom{sz-i}{2}}\)。设 \(f_{u,j}\)：表示以 \(u\) 为根的子树中，累计有 \(j\) 个叶子被“移除”的所有孩子分支的合并结果。这是一个背包卷积：\(g_u = \prod_{v \in ch(u)} h_v\)。容斥计算即可。