括号树
题意：给定一棵树，以 \(1\) 为根，每个点有字符 ( 或 )。
定义 \(s_i\) 为 \(i\) 到根的路径的子串中合法括号序列的个数，求 \(\bigoplus_{i = 1}^n i \times s_i\)，\(1 \le n \le 5 \times 10^5\)。
记 \(p_i\) 为 \(i\) 的父亲，\(a_i\) 为 \(i\) 到根的路径以 \(i\) 结尾的合法括号序列个数。
显然有 \(s_i = s_{p_i} + a_i\)，只要求 \(a_i\) 即可。
dfs 过程中模拟栈匹配，假设 \(i\) 是 ) 且能和某个未被匹配的 ( \(j\) 匹配，\(a_i = a_j + 1\)。
时间复杂度 \(O(n)\)。submission
划分
题意：长度为 \(n\) 的数组 \(\{a\}\)，求一个划分 \(S = \{p_1, p_2, \cdots, p_k\}\) 满足：
\[\sum_{i = 1}^{p_1}a_i \le \sum_{i = p_1 + 1}^{p_2}a_i \le \cdots \le \sum_{i = p_k + 1}^{n}a_i \]最小化
\[(\sum_{i = 1}^{p_1}a_i)^2 \le (\sum_{i = p_1 + 1}^{p_2}a_i)^2 \le \cdots \le (\sum_{i = p_k + 1}^{n}a_i)^2 \]数据范围：\(1 \le n \le 4 \times 10^7\)。
设 \(f(i, j)\) 表示长度为 \(i\) 的前缀，最后一个分割点在 \(j\) 的最小值：
\[f(i, j) =(s_i - s_j)^2 + \min_{(s_i - s_j)^2 \ge (s_j - s_k)^2}f(j, k) \]存在结论：\(f(i, j) \le f(i, j - 1)\)。
-
只有一个分割点，两部分分别为 \(x, y\)，在 \(y - x > 1\) 的前提下，\(x \gets x - 1,\ y \gets y - 1\) 显然更优。
-
否则设分割点数为 \(k\)，假设对于 \(1 \sim k - 1\) 都已经满足这个性质。
将最后一个点左移：
假设存在 \(j\)，使得 \(1 \sim j\) 保持不动，\((j + 1, k]\) 集体左移，在维持不降性质的同时使答案变小。
可以看作 \([p_j + 1, i]\) 上的一个子问题，而其规模小于 \(k\)，已经被证明不优了；
否则所有分割点集体左移，设第 \(i\) 段长度为 \(l_i\)，存在一种最优方案使前 \(k\) 段每段长度不增。
即：\(l_i \gets l_i - x_i,\ l_{k + 1} \gets l_{k + 1} + \sum x_i\)。
结论成立的一个充分条件为：\(l_i \gets l_i - 1,\ l_{k + 1} \gets l_{k + 1} + 1\) 不优，这是显然的。
因此每个 \(f(i)\) 的转一段是唯一的，记作 \(pre_i\)。
需要满足 \(s_i - s_{pre_i} \ge s_{pre_i} - s_{pre_{pre_i}}\)，移项即 $s_i \ge 2s_{pre_i} - s_{pre_{pre_i}} $。
单调栈找到最大的 \(j\) 满足 \(s_i \ge 2s_j - s_{pre_j}\)，那么 \(pre_i = j\)，时间复杂度 \(O(n)\)。
不是很懂为什么要卡空间，把 \(pre\) 处理出来后从后往前扫一遍即可，只要开一个 i128。
树的重心
题意：\(x\) 为树的中心当且仅当其最大子树大小不超过 \(\lfloor\frac{n}{2}\rfloor\)，一棵树只可能有一个或两个重心。
删去边 \(e\) 使整棵树分裂为两部分，求：
\[\sum_{e \in E}\bigg(\sum_{x\text{ 是 }T_1\text{ 的重心}}x + \sum_{y\text{ 是 }T_2\text{ 的重心}}y\bigg) \]数据范围：\(n \le 3\times 10^5\)。
选定原树的一个重心作为根 \(rt\)。
先考虑 \(x \ne rt\) 的情况。
如果断点一条边后 \(x\) 是重心，那么这条边不可能出现在 \(x\) 子树内。
记 \(s_x\) 为 \(x\) 子树大小，则 \(s_x \le \lfloor\frac{n}{2}\rfloor\)，如果断在子树内，则包含一棵大小为 \(n - s_x\) 的子树，与 \(x\) 是重心矛盾。
设 \(g_x\) 为 \(x\) 最大子树大小，\(S\) 为另一棵数的大小，需要满足：
\[\begin{cases} 2g_x\le n - S\\ \\ 2(n - S - s_x) \le n - S \end{cases} \]整理一下：
\[n - 2s_x \le S \le n - 2 g_x \]对于一个 \(x\)，要找满足以下条件的边的个数：
- \(n - 2s_x \le S \le n - 2 g_x\)。
- 不在 \(x\) 子树内。
只考虑第一个限制：对于 \(fa_u\) 到 \(rt\) 的链，\(S = n - s_y\)，其他地方 \(S = s_y\)，容易用树状数组维护。
利用出入子树时的增量把第二部分容斥掉（可以线段树合并）。
考虑 \(rt\) 作为根的次数，只关心最大子树 \(x\) 和次大子树 \(y\)，分类讨论断边位置即可。
树上的数
讲一下 CSP-S 史上最难题《树上的数》（只需入门组知识就能做的黑题）
标签：pre,le,重心,sum,子树,S2019,gets,CSP From： https://www.cnblogs.com/Luxinze/p/18471515