浅念づ昔夜's Blog

Lomsat gelral - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Solution

树上启发式合并模板题。

考虑暴力做法：设以 $i$ 为根的子树的答案为 $A_i$，每次求 $A_i$ 都重新遍历整棵子树。选择从 $1$ 开始往下 dfs，然后从子结点开始一个一个地求 $A_i$，时间复杂度为 $O(n^2)$。

Link

线性基 - OI Wiki (oi-wiki.org)

【模板】线性基 - 洛谷

传送门

Solution

设最大节点数为 $M$，因为第 $i$ 层最多有 $26^i$ 个节点，所以有 $M=\sum \limits ^m_{i=0}\min \{26^i,n\}$。

传送门

Solution

注意到 $S'_n$ 由左右两个相同的 $S'_{n-1}$ 夹着一个新字符 $S_n$ 拼接而来。所以可以尝试从 $S'_{n-1}$ 的答案转移得到 $S'_n$ 的答案。

传送门

Solution

设所有节点的权重之和为 $tot$，若 $tot$ 不能被 $3$ 整除，则问题无解。

传送门

Solution

设 $a_u$ 表示以 $u$ 为根的子树中，离 $u$ 最远的重要结点，$b_u$ 表示以 $u$ 为根的子树中，离 $u$ 次远的重要结点，$c_u$ 表示以 $u$ 为根的子树外离 $u$ 最远的结点。

传送门

Solution

使用扩展 KMP 求出 $z_i$。设字符串 $S$ 长度为 $n$，下标从 $0$ 开始。某前缀同时也是后缀，当且仅当 $i+z_i=n$。

传送门

Solution

区间 dp。设 $F_{l,r}$ 为删去区间 $[l,r]$ 的最小代价。显然，一个包含两种或以上字符的区间，它代价最小的删去方法中，一定存在一个断点将区间分成左右两半，使得这两个区间是各自删去的。

传送门

Solution

一棵子树中的所有点的 dfs 序必定连续，因此先 dfs 求出每个点的 dfs 序和深度，以及该子树的点的 dfs 序的左右边界。

传送门

Solution

设 $m=n\bmod p$，那么一定有 $m\le \dfrac{n}{2}$。因此每个点最多经过 $\log a_i$ 次取余就会变成 $1$。