浅念づ昔夜's Blog

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

Solution

容易得出结论：可选择的只有第一个染色点，且不妨将该点视作根结点。该点确定后，本题答案也就确定了为所有子树的大小之和。现在要求的是如何选择根结点，使得答案最大。

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

Solution

用倍增可以快速求出 $v_i$ 的 $p_i$ 级祖先 $u_i$，然后对 $u_i$ 打上标记，表示它与询问 $i$ 有关。标记可用 vector 维护。

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]$ 的最小代价。显然，一个包含两种或以上字符的区间，它代价最小的删去方法中，一定存在一个断点将区间分成左右两半，使得这两个区间是各自删去的。