小明の雜貨鋪

转化为树——树边和非树边 回忆 Tarjan 里讲的有向图 DFS 生成树： DFS 生成树 每当通过某条边访问到一个新节点，就加入这个点和这条边，并为点记录 DFS 序（unix 时间戳）。 DFS 生成树的边的种类： 树边 DFS 生成树上的边； 前向边 从某个点到它的某个子孙节点的边，产生了捷径。 反向边 从某个点到它的某个祖先节点的边，产生了环； 横叉边 从某个点到一个既非它子孙节点、也非它祖先节点的边，连接了两个强连通子图。 对于无向图是类似的，不同点是 无向图的 DFS 树没有横叉边 ，只有前向边和反向边，而前向边都是已访问的，可以认为 无向图的 DFS 树只有反向边，因此非树边的端点 u,vu,vu,v 的 LCA 为 vvv，作树上差分时，直接 wv−d, wu+dw_{v}-d,\ w_{u}+dwv​−d, wu​+d 即可。 删边后的连通性 给定一个无向连通图。每次询问给出一组边，确定删除这些边后图是否连通。 令第 iii 条非树边的权值是 2i2^i2i，再令这条边的两个端点在树上的对应路径上的边全部 ⊕2i\oplus...

二分图 Stop the Castle There are n castles and m obstacles on a chessboard. Each castle or obstacle occupies exactly one cell and all occupied cells are distinct. Two castles can attack each other, if they’re on the same row or the same column, and there are no obstacles or other castles between them. Find a way to place the minimum number of additional obstacles onto the chessboard, so that no two castles can attack each...

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

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

二叉树 先序遍历：先遍历根节点，然后遍历左节点，最后遍历右节点 中序遍历：先遍历左节点，然后遍历根节点，最后遍历右节点（大概可以理解为把树平面投影至二维从左到右） 后序遍历：先遍历左节点，然后遍历右节点，最后遍历根节点 树上差分 Adjacent Difference on Tree 问题 每次操作将树上 u→vu\to vu→v 路径上的所有点权增加 ddd，求每个点的点权。 思路 用类似前缀和的思想存储树上的点权。用 val[p] 存储 ppp 节点上方的点权增加值，对于上述操作，按差分思想，只需 12val[u] += d; val[v] += d;val[lca(u,v)] -= d; val[p[lca(u,v)] -= d; 复原时，从根节点开始一步步累加。 1234567void dfs2(int u, int p = 0) { for (auto& v : E[u]) { if (v == p) continue; dfs2(v, u); val[u]...

在树上，我们可以任选一个节点作为根节点，从而定义出每个节点的深度和每棵子树的根。 在 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 的过程中，将子树的信息合并到父节点上。 线段树合并暂时不支持区间修改。 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); ...

12345678910111213141516171819202122232425262728293031323334353637383940414243444546/** 一维前缀和 **/vector<ll> pre(n + 1);for (int i = 0; i < n; i++) { pre[i + 1] = pre[i] + a[i];}// 查询 [l, r)auto get = [&](int l, int r) { return pre[r] - pre[l];};/** 二维前缀和 **/vector s(m + 1, vector<ll>(n + 1));for (int x = 0; x < m; x++) { for (int y = 0; y < n; y++) { s[x + 1][y + 1] = s[x + 1][y] + s[x][y + 1] - s[x][y] + a[x][y]; }}//...