小明の雜貨鋪

树具有天然的合并性质，即某节点的子树信息全部来自于它子节点的子树信息。因此先计算子节点，再计算父节点，在树上 DFS 的过程中，将子树的信息合并到父节点上。 线段树合并暂时不支持区间修改。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667template<class info>struct SMT { int L, R, pcnt; vector<info> t; vector<int> ls, rs; vector<int> rt; SMT() { init(0, 0); t.resize(N << 2); ls.resize(N << 2); rs.resize(N << 2); ...

两次 DFS 求树直径 时空复杂度 Θ(n)\Theta(n)Θ(n)。 123456789101112131415161718192021vector<int> p(n), path;auto find = [&](int s) { vector<int> dep(n, -1); auto dfs = [&](this auto&& dfs, int u) -> void { for (auto v : E[u]) { if (~dep[v]) continue; dep[v] = dep[u] + 1; // 如果带点权 dep[v] = dep[u] + val[v]; // 如果带边权 dep[v] = dep[u] + w; p[v] = u; dfs(v); } }; ...

树链剖分 把一棵树分割成若干条链，以便于维护（路径、子树）信息。 重链剖分 重链剖分 (Heavy Path Decomposition) 从树上每个 轻节点 出发，不断向下走 重边，构成一条链。任意点恰好在一条重链中。任意点到根的路径为 Θ(log⁡n)\Theta(\log n)Θ(logn) 条重链和轻边交替形成。 使用两次 DFS 完成重链剖分，时空复杂度 Θ(n)\Theta(n)Θ(n)。 若 u,vu,vu,v 在同一条链上，LCA 是深度较小的那个节点；否则，将链头深度较大的节点跳转到其链头的父节点上，直至两点在同一条链上。复杂度 Θ(n)−Θ(log⁡n)\Theta(n) - \Theta(\log n)Θ(n)−Θ(logn)。 回忆 树的 DFS 序：每个节点在 DFS 中的进出栈的时间序列。每棵子树的 DFS 序都是连续的，且子树上根节点 DFS 序最小；而且，如果优先遍历重子节点，那么同一条链上的节点的 DFS 序也是连续的，且链头节点 DFS 序最小。因此，uuu 的子树上所有节点的编号介于 dfsn[u] 和 dfsnR[u] 之间，其中...

判断无根树是否同构，时间复杂度 Θ(∑n)\Theta\left(\sum n \right)Θ(∑n)。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include <bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;mt19937_64 rng{ chrono::steady_clock::now().time_since_epoch().count() };const int N = 3e5 + 8;ull hsh[N];int main() { for (int i = 0; i < N; i++) { hsh[i] = rng(); ...

树的重心 树的重心要么 惟一 ，要么 有两个，且这两个重心相邻。 以树的重心为根时，所有子树的大小都不超过整棵树大小的一半，即 siz[v] * 2 < siz[u]。 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。 把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。 求树的重心 1234567891011121314151617vector<int> siz(n), mss(n); // 固定根时的子树大小 最大子树大小auto dfs = [&](this auto&& dfs, int u, int p) -> void { siz[u] = 1; for (auto v : E[u]) { if (v == p) continue; dfs(v, u); siz[u] += siz[v];...

Strings 子序列 将若干元素提取出来并不改变相对位置形成的序列，不一定连续。 子串 连续的子序列。 后缀 （Suffix）从某位置到整个串末尾结束的子串。 前缀 （Prefix）从串首开始到某位置结束的子串。 字典序 以第 iii 个字符作为第 iii 关键字进行大小比较，空字符小于字符集内任何字符。

Given a text s[] and a pattern p[], print all occurrences of p[] in s[]. Brute force solution 最坏时间复杂度 Θ(mn)\Theta(mn)Θ(mn)。 12345678910int i = 0, j = 0;while (i < s.length()) { if (s[i] == T[j]) ++i, ++j; else i = i-j+1, j = 0; if (j == T.length()) { // 匹配成功 printf("[%d-%d] ", i-j, i-1); i = i - j + 1; j = 0; }} KMP Algorithm ——Knuth-Morris-Pratt 字符串查找算法 PMT（Partial Match Table，部分匹配表...

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include <bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;using ulll = __uint128_t;constexpr int N = 1e6 + 8;constexpr ull mod = (1ull << 61) - 1;mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());uniform_int_distribution<ull> dist(mod / 2, mod - 1);const ull H = dist(rnd);struct mull { ull x; constexpr...

char ascii 0 48 9 57 A 65 Z 90 a 97 z 122 经典字典树 主机场 给定一组字符串 s1,s2,⋯ ,sns_1,s_2,\cdots,s_ns1​,s2​,⋯,sn​，任选 kkk 个 sa1,sa2,⋯ ,sak (ai≠aj)s_{a_1},s_{a_2},\cdots,s_{a_k}\ (a_{i}\ne a_{j})sa1​​,sa2​​,⋯,sak​​ (ai​=aj​)，最小化 max⁡1⩽i,j⩽k,i≠jlcp⁡(sai,saj)\max\limits_{1 \leqslant i,j \leqslant k,i\ne j}^{}\operatorname{lcp}(s_{a_i},s_{a_j})1⩽i,j⩽k,i=jmax​lcp(sai​​,saj​​)。其中 lcp⁡(p,q)\operatorname{lcp}(p,q)lcp(p,q) 是字符串 ppp 和字符串 qqq...

后缀数组 后缀数组 (Suffix Array, SA) 是把字符串的所有 后缀 按 字典序 排序后得到的数组。 定义： 排名数组 rk⁡w(i)\operatorname{rk}_w(i)rkw​(i)：从第 iii 位开始、长度为 www 的子串在所有长度为 www 的子串中的排名； 编号数组 sa⁡w(i)\operatorname{sa}_w(i)saw​(i)：长度为 www 的子串中字典序第 iii 小的一个的开始位置，与排名数组互逆，即 sa⁡(rk⁡(i))=i\operatorname{sa}(\operatorname{rk}(i))=isa(rk(i))=i，rk⁡(sa⁡(i))=i\operatorname{rk}(\operatorname{sa}(i))=irk(sa(i))=i。 用倍增法在 Θ(nlog⁡n)\Theta(n\log n)Θ(nlogn)...