小明の雜貨鋪

DSU01 - Find by Optimized Path Compression 路径压缩优化 12345678910111213141516171819202122232425262728struct DSU { vector<int> p, siz; DSU(int n) : p(n + 1), siz(n + 1, 1) { iota(p.begin(), p.end(), 0); } int find(int x) { while (x != p[x]) x = p[x] = p[p[x]]; // 路径压缩 return x; } bool same(int x, int y) { return find(x) == find(y); } bool uno(int x, int y) { x = find(x), y =...

在树上，我们可以任选一个节点作为根节点，从而定义出每个节点的深度和每棵子树的根。 在 DP 的状态表示中，第一维通常是节点编号，第二维代表状态基 。大多数时候，我们采用 递归 的方式实现树形动态规划。对于每一个节点 xxx，先递归它的每一个子节点上进行 DP ，在 回溯时，从子节点向节点 xxx 进行状态转移。 有根树的树形 DP 树背包 有根树，有点权。mmm 元点集 SSS 满足：若子节点 ∈S\in S∈S，则父节点 ∈S\in S∈S。最大化 SSS 点权和。 123456789101112int n, m, w[N], dp[N][M];auto dfs = [&](this auto&& dfs, int u) -> void { dp[u][1] = w[u]; for (auto& v : E[u]) { dfs(v); for (int k = m; k >= 1; --k) { for (int i = k; i...

树链剖分 把一棵树分割成若干条链，以便于维护（路径、子树）信息。 重链剖分 重链剖分 (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] 之间，其中...

两次 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); } }; ...

树的重心 树的重心要么 惟一 ，要么 有两个，且这两个重心相邻。 以树的重心为根时，所有子树的大小都不超过整棵树大小的一半，即 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];...

树具有天然的合并性质，即某节点的子树信息全部来自于它子节点的子树信息。因此先计算子节点，再计算父节点，在树上 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); ...

判断无根树是否同构，时间复杂度 Θ(∑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(); ...

斐波那契数列的 20 种求法 矩阵快速幂 题意 设 an={an−1+an−2,n⩾31,n=1∨n=2a_{n}=\begin{cases}a_{n-1}+a_{n-2},&n \geqslant 3\\1,&n=1\lor n=2\end{cases}an​={an−1​+an−2​,1,​n⩾3n=1∨n=2​，求 an mod ma_n\bmod man​modm。 解 设 M=[0111]\mathbf{M}=\begin{bmatrix}0 &1\\ 1 & 1\end{bmatrix}M=[01​11​]​，则 [Fn0Fn+10]=Mn−1[1010]\begin{bmatrix}F_n & 0 \\ F_{n+1} & 0\end{bmatrix} =\mathbf{M}^{n-1}\begin{bmatrix}1 & 0 \\ 1 & 0 \end{bmatrix} [Fn​Fn+1​​00​]=Mn−1[11​00​] 于是...

博弈论 是经济学的一个分支； 主要研究具有竞争或对抗性质的对象在一定规则下的行为； 考虑个体中的预测行为和实际行为，并研究其优化策略； 通俗地讲，主要研究的是在一个游戏中进行游戏的多位玩家的策略。 公平组合游戏（ICG） 二人参与，轮流决策，每次可以在有限的合法决策集合中选择一种进行操作，双方均知道游戏的完整信息； 在某一确定状态做出的决策集合只与状态有关，与玩家、之前的操作等任何因素都无关； 如果轮到某位玩家的回合时合法决策集合为空（即无法进行操作），该名玩家负。游戏一定会在有限步数之后以非平局结束； 大部分棋类游戏都是非公平组合游戏：国际象棋，五子棋等，因为双方都无法使用对方的棋子。 博弈图 给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。 任何一个 ICG 游戏都可以转化为有向图游戏：把每个状态视为一个节点，向它的后继状态连边，转化为有向图游戏，也称绘制了它的博弈状态图（简称博弈图或者游戏图）。 ...

裂项 ∑i=1n(ai−ai+k)=∑i=1kai−∑i=n+1n+kai\sum_{i=1}^{n}(a_{i}-a_{i+k})=\sum_{i=1}^{k}a_{i}-\sum_{i=n+1}^{n+k}a_{i} i=1∑n​(ai​−ai+k​)=i=1∑k​ai​−i=n+1∑n+k​ai​ 约瑟夫环问题 约瑟夫环问题 设 Jn,mJ_{n, m}Jn,m​ 表示规模分别为 n,mn, mn,m 的约瑟夫问题的答案。我们有如下递归式 Jn,m=(Jn−1,m+m) mod nJ_{n, m}=\left(J_{n-1, m}+m\right) \bmod n Jn,m​=(Jn−1,m​+m)modn 这个也很好推。从 0 开始数 mmm 个，让第 m−1m-1m−1 个人出局后剩下 n−1n-1n−1 个人，计算出在 n−1n-1n−1 个人中选的答案后，再加一个相对位移 mmm 得到真正的答案。 题目说是从 kkk 开始报数，所以答案再加上 kkk。 时间复杂度 Θ(n)\Theta(n)Θ(n)： 12345int res = 0;for (int i =...