树链剖分
重剖
对于一棵 \(n\) 个点的树,我们定义一个点的重儿子为它的所有儿子中子树大小最大的。
一个点与其重儿子的连边为重边,其他边为轻边。
定义重链为由若干条首尾相连的重边连成的极长链。
即(图源:OI-Wiki):
重链有很好的性质:
- 设以 \(u\) 为根的子树大小为 \(siz_u\),则有其轻儿子的 \(siz_v\) 一定不超过 \(\frac {siz_u}2\)。证明:若 \(siz_v > \frac{siz_u}2\),则一定不存在另一个儿子 \(v'\),使得 \(siz_{v'}\ge siz_v\),所以此时 \(v\) 一定不是轻儿子。
- 任意两条重链都是不交的。证明:考虑两条重链相交一定存在一个点连接了超过两条重边,即除其父亲与该点的重边外,该点仍向儿子连了两条重边,而一个点最多有一个重儿子,矛盾。
- 从树上的某个点到其祖先的过程中,最多经过不超过 \(\mathcal{O}(\log n)\) 条轻边。证明:过程中每经过一条边,就相当于当前点的 \(siz_u\) 变为 \(siz_{\mathrm{fa}_u}\)。如果经过的边为轻边,则根据第一个性质,有 \(siz_{\mathrm{fa}_u}\ge2siz_u\),即每经过一条轻边,当前子树大小至少扩大 \(2\) 倍。最多有 \(n\) 个点,故最多扩大 \(\mathcal{O}(\log n)\) 次。
- 若 dfs 时先走重儿子,再走轻儿子,则对于每条重链在该 dfs 序上一定是一段连续区间。证明:容易发现一定先走完一段连续的重边才走轻边,即先走完一条完整重链才走下一条。
根据这些性质,重链剖分就可以把树上两点间的路径问题转化成 \(\mathcal{O}(\log n)\) 段区间问题。
重剖模板:- // dep[u] : u的深度
- // fa[u] :u的直接父亲
- // siz[u] : 以 u 的子树大小
- // son[u] : u的重儿子
- // top[u] : u所在重链的深度最小的点
- void dfs(int u) {
- dep[u] = dep[fa[u]] + 1, siz[u] = 1;
- for (const int& v : e[u])
- if (v != fa[u]) {
- fa[v] = u, dfs(v), siz[u] += siz[v];
- if (siz[v] > siz[son[u]]) son[u] = v;
- }
- }
- void dfs(int u, int tp) {
- top[u] = tp, dfn[num[u] = ++idx] = u;
- if (son[u]) dfs(son[u], tp);
- for (const int& v : e[u])
- if (v != fa[u] && v != son[u])
- dfs(v, v);
- }
复制代码 [LuoguP4211] [LNOI2014] LCA
pro.
给一棵 \(n\) 个点的有根树,\(m\) 次询问,每次询问给定 \(l,r,z\),求 \(\sum_{i=l}^rdep_{\mathrm{lca}(i,z)}\)。
\(n,m\le5e4\)。\(1\mathrm{s},125\mathrm{MB}\)。
sol.
考虑暴力怎么做:每次询问枚举 \(i\),暴力求 \(\mathrm{lca}(i,z)\) 统计答案。
显然优化要么快速求出一堆点与某个定点的 \(\mathrm{lca}\),要么考虑把 \(\mathrm{lca}\) 转化。
前者显然不好做。
Trick:发现 \(dep_{\mathrm{lca}(i,z)}\) 等价于 \(i\) 和 \(z\) 的公共祖先个数。
我们给 \(i\) 到根的链上的点全部赋一个 \(1\) 的权值,则从 \(z\) 到根的链上的点权和即为答案。
考虑对于每个 \(z\),我们让 \([l,~r]\) 的每个点到根链做一遍赋值,累加权值,最后统计 \(z\) 的根链和即为答案。
于是我们把不容易维护的 \(\mathrm{lca}\) 转化为了容易维护的根链加和根链查询和,树剖线段树很容易维护。
但这导致询问之间可能有相互影响,所以每次查询要清空线段树,复杂度难以接受。
把询问拆成 \([0,~r]-[0,~l-1]\),然后离线询问,从 \([1,~n]\) 依次修改,每到一个点就在对应的询问上统计权值,复杂度 \(\mathcal{O}\big((n+m)\log^2 n\big)\)。
cod.
- #include <bits/stdc++.h>
- #define file(name, suf) ""#name"."#suf""
- #define input(name) freopen(file(name, in), "r", stdin)
- #define output(name) freopen(file(name, out), "w", stdout)
- constexpr int N = 5e4 + 10, Mod = 201314;
- int n, m, idx, fa[N], dep[N], siz[N], son[N], top[N], num[N];
- std::vector<int> e[N];
- struct Query { int r, z, ans, id; } q[N << 1];
- struct Seg_Tree {
- struct Node { int len, sum, add; } t[N << 2];
- #define ls (u << 1)
- #define rs (u << 1 | 1)
- #define mid ((l + r) >> 1)
- void up(int u) { t[u].sum = (t[ls].sum + t[rs].sum) % Mod; }
- void build(int u, int l, int r) {
- t[u] = {r - l + 1, 0, 0};
- if (l == r) return;
- build(ls, l, mid), build(rs, mid + 1, r);
- }
- void add(int u, int x) {
- t[u].sum = (t[u].sum + 1ll * x * t[u].len % Mod) % Mod;
- t[u].add = (t[u].add + x) % Mod;
- }
- void down(int u) {
- if (t[u].add) add(ls, t[u].add), add(rs, t[u].add), t[u].add = 0;
- }
- void add(int u, int l, int r, int ql, int qr, int x) {
- if (l > qr || r < ql) return;
- if (l >= ql && r <= qr) return add(u, x);
- down(u);
- add(ls, l, mid, ql, qr, x), add(rs, mid + 1, r, ql, qr, x), up(u);
- }
- int query(int u, int l, int r, int ql, int qr) {
- if (l > qr || r < ql) return 0;
- if (l >= ql && r <= qr) return t[u].sum;
- down(u);
- return (query(ls, l, mid, ql, qr) + query(rs, mid + 1, r, ql, qr)) % Mod;
- }
- } T;
- void dfs(int u) {
- dep[u] = dep[fa[u]] + 1, siz[u] = 1;
- for (const int& v : e[u])
- if (v != fa[u]) {
- fa[v] = u, dfs(v), siz[u] += siz[v];
- if (siz[v] > siz[son[u]]) son[u] = v;
- }
- }
- void dfs(int u, int tp) {
- top[u] = tp, num[u] = ++idx;
- if (son[u]) dfs(son[u], tp);
- for (const int& v : e[u])
- if (v != fa[u] && v != son[u])
- dfs(v, v);
- }
- void add(int u, int v, int x) {
- while (top[u] != top[v]) {
- if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
- T.add(1, 1, n, num[top[u]], num[u], 1);
- u = fa[top[u]];
- }
- if (dep[u] > dep[v]) std::swap(u, v);
- T.add(1, 1, n, num[u], num[v], 1);
- }
- int query(int u, int v) {
- int res = 0;
- while (top[u] != top[v]) {
- if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
- res = (res + T.query(1, 1, n, num[top[u]], num[u])) % Mod;
- u = fa[top[u]];
- }
- if (dep[u] > dep[v]) std::swap(u, v);
- return (res + T.query(1, 1, n, num[u], num[v])) % Mod;
- }
- void solve() {
- std::cin >> n >> m, T.build(1, 1, n);
- for (int i = 2; i <= n; i++) {
- int f;
- std::cin >> f, ++f;
- e[i].push_back(f), e[f].push_back(i);
- }
- for (int i = 1; i <= m; i++) {
- int l, r, z;
- std::cin >> l >> r >> z, ++l, ++r, ++z;
- q[i].r = l - 1, q[i].z = z;
- q[i + m].r = r, q[i + m].z = z;
- q[i].id = q[i + m].id = i;
- }
- dfs(1), dfs(1, 1);
- std::sort(q + 1, q + (m << 1) + 1, [](const Query& a, const Query& b) { return a.r < b.r; });
- int now = 1;
- while (now <= m << 1 && q[now].r < 1) now++;
- for (int i = 1; i <= n; i++) {
- add(1, i, 1);
- while (now <= m << 1 && q[now].r == i)
- q[now].ans = query(1, q[now].z), now++;
- }
- std::sort(q + 1, q + (m << 1) + 1, [](const Query& a, const Query& b) { return a.id == b.id ? a.r < b.r : a.id < b.id; });
- for (int i = 1; i <= m << 1; i += 2) std::cout << ((q[i + 1].ans - q[i].ans) % Mod + Mod) % Mod << "\n";
- }
- int main() {
- // input(Test), output(Test);
- int _ = 1;
- // std::cin >> _;
- while (_--) solve();
- return 0;
- }
复制代码 [LuoguP6798] 简单的树
pro.
给一棵 \(n\) 个点的有根树,点有点权 \(c_i\)。
定义点 \(u\) 的 \(val_u\) 为 \(\max_{v\in\mathrm{substree}_u}c_v\)。
定义函数 \(f(x,y)\) 为将 \(c_x\) 修改为 \(y\) 时整棵树的 \(\sum val_u\)。
\(q\) 次询问,每次询问给定 \(l,r,a\),求 \(\sum_{i=l}^rf(a,i)\)。
强制在线。\(n,q\le5e5\)。\(\mathrm{3s,500MB}\)。
sol.
考虑 \(f(x,y)\) 怎么求。
容易发现修改 \(c_x\) 仅会影响到 \(x\) 及其祖先的 \(val\),所以预处理出每条链上的 \(val\) 之和 \(dis\),其他点的贡献即为整棵树的答案减去 \(dis_x\)。所以仅需要考虑修改后 \(x\) 根链的变化即可。
而每个点上将 \(c_x\) 改为 \(y\) 的答案等于删去 \(x\) 后的答案与 \(y\) 取较大值。于是对于 \(x\) 的某个祖先 \(u\),若 \(val_u=c_x\),则删去后的 \(val_u\) 应该等于子树中点权的次大值;否则不变,即子树中的最大值。于是我们可以 \(\mathcal{O}(n^2)\) 的回答一个询问。
观察 \(val_u\) 的定义,容易发现从一个点到根的路径上的点,\(val\) 单调不降。
于是必然存在某个 \(p\),使得 \(x\) 到 \(p\) 的路径上的所有点均为次大值,\(\mathrm{fa}_p\) 到根的路径上的所有点均为最大值,故通过倍增即可 \(\mathcal{O}(\log n)\) 的找到 \(p\),单次询问 \(\mathcal{O}(n\log n)\)。
发现我们要求的实际上是 \(\sum_{i=l}^r\sum\max(ans_u,i)\),其中 \(u\) 为 \(x\) 的根链上的点, \(ans_u\) 为删去 \(x\) 后 \(u\) 的 \(val\)。
看到 \(\sum_{i=l}^r\) 的经典Trick就是差分为 \(\sum_{i=0}^r-\sum_{i=0}^{l-1}\),于是我们只考虑 \(\sum_{i=0}^rf(a,i)\)。
考虑每个 \(u\),若 \(ans_u\ge r\),则贡献为 \(ans_u(r+1)\) ;否则,贡献为
\[\sum_{i=0}^r\max(ans_u,i)=\sum_{i=0}^{ans_u}ans_u+\sum_{i=ans_u+1}^ri=\frac{ans_u^2+ans_u+r^2+r}2\]
又由于之前的单调不降性质,对于 \(x\) 到 \(p\) 和 \(\mathrm{fa}_p\) 到根的路径上第一个满足 \(val_u\ge r\) 的点也是可以倍增的,即:
于是树剖后只需要用前缀和维护区间最大值、次大值的和、平方和即可。
实现时注意由于 \(lp,p,rp\) 的是否存在而导致的边界问题,细节较多。
cod.
- #include <bits/stdc++.h>
- #define file(name, suf) ""#name"."#suf""
- #define input(name) freopen(file(name, in), "r", stdin)
- #define output(name) freopen(file(name, out), "w", stdout)
- constexpr int N = 1e5 + 10;
- int n, m, idx, fa[N], dep[N], son[N], siz[N], top[N], dfn[N], num[N];
- std::vector<int> e[N];
- struct Node {
- int l, r, len, ans, cvr;
- Node operator + (const Node& b) {
- Node res{};
- res.ans = ans + b.ans + (r == b.l);
- res.len = len + b.len;
- res.l = l ? l : b.l, res.r = b.r ? b.r : r;
- return res;
- }
- };
- struct Seg_Tree {
- Node t[N << 2];
- #define ls (u << 1)
- #define rs (u << 1 | 1)
- #define mid ((l + r) >> 1)
- void build(int u, int l, int r) {
- t[u].len = r - l + 1, t[u].ans = 0;
- if (l == r) return t[u].l = t[u].r = l, void();
- build(ls, l, mid), build(rs, mid + 1, r), t[u] = t[ls] + t[rs];
- }
- void cover(int u, int x) {
- t[u].l = t[u].r = t[u].cvr = x;
- t[u].ans = t[u].len - 1;
- }
- void down(int u) {
- if (t[u].cvr) cover(ls, t[u].cvr), cover(rs, t[u].cvr), t[u].cvr = 0;
- }
- void cover(int u, int l, int r, int ql, int qr, int x) {
- if (l > qr || r < ql) return;
- if (l >= ql && r <= qr) return cover(u, x);
- down(u);
- cover(ls, l, mid, ql, qr, x), cover(rs, mid + 1, r, ql, qr, x), t[u] = t[ls] + t[rs];
- }
- int query(int u, int l, int r, int k) {
- if (l == r) return t[u].l;
- down(u);
- if (k <= mid) return query(ls, l, mid, k);
- else return query(rs, mid + 1, r, k);
- }
- Node query(int u, int l, int r, int ql, int qr) {
- if (l > qr || r < ql) return {0, 0, 0, 0, 0};
- if (l >= ql && r <= qr) return t[u];
- down(u);
- return query(ls, l, mid, ql, qr) + query(rs, mid + 1, r, ql, qr);
- }
- } T;
- void dfs(int u) {
- dep[u] = dep[fa[u]] + 1, siz[u] = 1;
- for (const int& v : e[u])
- if (v != fa[u]) {
- fa[v] = u, dfs(v), siz[u] += siz[v];
- if (siz[v] > siz[son[u]]) son[u] = v;
- }
- }
- void dfs(int u, int tp) {
- dfn[num[u] = ++idx] = u, top[u] = tp;
- if (son[u]) dfs(son[u], tp);
- for (const int& v : e[u])
- if (v != fa[u] && v != son[u])
- dfs(v, v);
- }
- void cover(int u, int v, int x) {
- while (top[u] != top[v]) {
- if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
- T.cover(1, 1, n, num[top[u]], num[u], x);
- u = fa[top[u]];
- }
- if (dep[u] > dep[v]) std::swap(u, v);
- T.cover(1, 1, n, num[u], num[v], x);
- }
- int query(int u, int v) {
- Node L{}, R{}, res{};
- while (top[u] != top[v]) {
- if (dep[top[u]] > dep[top[v]]) {
- res = T.query(1, 1, n, num[top[u]], num[u]);
- std::swap(res.l, res.r);
- L = L + res;
- u = fa[top[u]];
- } else {
- res = T.query(1, 1, n, num[top[v]], num[v]);
- R = res + R;
- v = fa[top[v]];
- }
- }
- if (dep[u] < dep[v]) {
- res = T.query(1, 1, n, num[u], num[v]);
- res = L + res + R;
- } else {
- res = T.query(1, 1, n, num[v], num[u]);
- std::swap(res.l, res.r);
- res = L + res + R;
- }
- return res.ans;
- }
- void solve() {
- std::cin >> n >> m, T.build(1, 1, n), idx = 0;
- for (int i = 1; i <= n; i++) e[i].clear(), son[i] = 0;
- for (int i = 1; i < n; i++) {
- int u, v;
- std::cin >> u >> v;
- e[u].push_back(v), e[v].push_back(u);
- }
- dfs(1), dfs(1, 1);
- for (int i = 1; i <= m; i++) {
- int op, u, v;
- std::cin >> op >> u >> v;
- if (op == 1) cover(u, v, i + n);
- else std::cout << query(u, v) << "\n";
- }
- }
- int main() {
- // input(Test), output(Test);
- std::cin.tie(nullptr)->sync_with_stdio(false);
- int _ = 1;
- std::cin >> _;
- while (_--) solve();
- return 0;
- }
复制代码 [QOJ9492] 树上简单求和
pro.
给定两棵 \(n\) 个点的有编号无根树(形态不保证相同),点的编号从 \(1\) 到 \(n\),点 \(i\) 的点权为 \(a_i\),两棵树共用点权。
有 \(m\) 次操作,每次操作给定 \(x,y,k\),进行两步:
先对第一棵树上 \(x\) 到 \(y\) 的简单路径上的所有点的权值增加 \(k\) ;
再求出第二棵树上 \(x\) 到 \(y\) 的简单路径上的所有点的权值和,对 \(2^{64}\) 取模。
\(n,m\le 2e5\)。 \(\mathrm{6s,256MB}\)。
sol.
首先如果树是一条链,那么就变成了二维平面 \(x\) 区间加, \(y\) 区间和,可以规约矩阵乘法。所以本题显然不存在 \(\mathrm{poly} \log\) 的做法。
显然我不会规约矩乘
人话就是本题最优只能做到 \(\mathcal{O}(\sqrt n)\)。
树剖专题就不用其他科技了其实是我不会树分块,只做到 \(\mathcal{O}(m\sqrt n\log n)\),可以通过。
首先通过树剖可以把树链操作转化为 \(\mathcal{O}(\log n)\) 个 dfs 序上的区间问题,所以以下只考虑区间问题。
假设我们已经实现了一个数据结构,支持在 \(\mathcal{O}(x)\) 的复杂度内对第二个序列单点修改,在 \(\mathcal{O}(y)\) 的复杂度内对第二个序列区间查询。
考虑如何修改:对第一个序列分块,散块直接暴力在第二个序列上单点修改,查询时通过第二个序列区间查询,共 \(\mathcal{O}(m\sqrt n)\) 次修改, \(\mathcal{O}(m)\) 次查询,故散块修改复杂度为 \(\mathcal{O}(mx\sqrt n)\),查询复杂度为 \(\mathcal{O}(my)\)。为了根号平衡,我们发现,第二个序列上的数据结构应该支持 \(\mathcal{O}(1)\) 单点修改, \(\mathcal{O}(\sqrt n)\) 区间查询——还是分块。
整块修改依然考虑延迟标记,问题在于如何在查询时加入影响。
考虑前缀和,对于第一个序列的每个块,我们 \(\mathcal{O}(n)\) 预处理出第二个序列的每个前缀有多少个点落在该块内,区间查询时该块的对答案的影响为 \(tag_i\cdot (pre_{i,r}-pre_{i,l-1})\)。整块修改和查询都有 \(\mathcal{O}(m\sqrt n)\) 次,单次 \(\mathcal{O}(1)\),故整块修改和查询复杂度均为 \(\mathcal{O}(m\sqrt n)\)。
于是算上树剖就可以在 \(\mathcal{O}(m\sqrt n\log n)\) 的时间内在线解决本题。
然后就被卡空间了(
但空间复杂度 \(\mathcal{O}(n\sqrt n)\approx9e7\),大概在 \(\mathrm{350MB}\) 左右。
考虑优化空间,如果不维护序列的每个前缀,而仅维护整块的每个前缀,那么空间就变成了 \(\mathcal{O}(n)\) 的。
于是我们可以在 \(\mathcal{O}(\sqrt n)\) 的时间内解决整块对整块的影响,还需处理整块对散块的影响。
显然对于每个点有且仅有一个块将其包含,于是对每个散块的影响容易 \(\mathcal{O}(1)\) 查询。
于是做完了。时间 \(\mathcal{O}(m\sqrt n\log n)\),空间 \(\mathcal{O}(n)\)。
实测块长 \(200\) 左右比较快。
cod.
- #include <bits/stdc++.h>
- #define file(name, suf) ""#name"."#suf""
- #define input(name) freopen(file(name, in), "r", stdin)
- #define output(name) freopen(file(name, out), "w", stdout)
- typedef long long ll;
- constexpr int N = 5e5 + 10, Mod = 998244353;
- int n, q, opt, c[N], inv_2;
- int idx, f[20][N], dep[N], siz[N], son[N], top[N], dfn[N], num[N];
- int m[N], nm[N], dis[N], s[4][N], ans;
- std::vector<int> e[N];
- ll qpow(ll a, ll b) {
- ll res = 1;
- while (b) {
- if (b & 1) res = res * a % Mod;
- a = a * a % Mod, b >>= 1;
- }
- return res;
- }
- void dfs(int u) {
- m[u] = c[u], dep[u] = dep[f[0][u]] + 1, siz[u] = 1;
- for (int i = 1; (1 << i) <= dep[u]; i++) f[i][u] = f[i - 1][f[i - 1][u]];
- for (const int& v : e[u])
- if (v != f[0][u]) {
- f[0][v] = u, dfs(v), siz[u] += siz[v];
- if (siz[v] > siz[son[u]]) son[u] = v;
- if (m[v] > m[u]) nm[u] = m[u], m[u] = m[v];
- else if (m[v] > nm[u]) nm[u] = m[v];
- if (nm[v] > nm[u]) nm[u] = nm[v];
- }
- }
- void dfs(int u, int tp) {
- top[u] = tp, dfn[num[u] = ++idx] = u, dis[u] = (dis[f[0][u]] + m[u]) % Mod;
- if (son[u]) dfs(son[u], tp);
- for (const int& v : e[u])
- if (v != f[0][u] && v != son[u])
- dfs(v, v);
- }
- int query(int u, int v, int k) {
- int res = 0;
- while (top[u] != top[v]) {
- if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
- res = (res + s[k][num[u]] - s[k][num[top[u]] - 1]) % Mod;
- u = f[0][top[u]];
- }
- if (dep[u] > dep[v]) std::swap(u, v);
- return (res + s[k][num[v]] - s[k][num[u] - 1]) % Mod;
- }
- int query(int a, int r) {
- int p = a, res = 1ll * (s[0][n] - dis[a]) * (r + 1) % Mod;
- if (m[a] == c[a]) {
- for (int i = std::__lg(dep[a]); ~i; i--) if (f[i][p] && m[f[i][p]] == c[a]) p = f[i][p];
- if (nm[a] >= r) {
- res = (res + 1ll * query(a, p, 2) * (r + 1) % Mod) % Mod;
- } else {
- int lp = a;
- for (int i = std::__lg(dep[a] - dep[p] + 1); ~i; i--) {
- if (dep[f[i][lp]] >= dep[p] && nm[f[i][lp]] < r)
- lp = f[i][lp];
- }
- res = (res + (1ll * (query(a, lp, 3) + query(a, lp, 2)) % Mod + 1ll * r * (r + 1) % Mod * (dep[a] - dep[lp] + 1) % Mod) % Mod * inv_2 % Mod) % Mod;
- if (lp != p) {
- res = (res + 1ll * query(f[0][lp], p, 2) * (r + 1) % Mod) % Mod;
- }
- }
- if (p == 1) return (res + Mod) % Mod;
- p = f[0][p];
- }
- if (m[p] >= r) {
- res = (res + 1ll * query(p, 1, 0) * (r + 1) % Mod) % Mod;
- } else {
- int rp = p;
- for (int i = std::__lg(dep[p] - 1); ~i; i--) {
- if (f[i][rp] && m[f[i][rp]] < r)
- rp = f[i][rp];
- }
- res = (res + (1ll * (query(p, rp, 1) + query(p, rp, 0)) % Mod + 1ll * r * (r + 1) % Mod * (dep[p] - dep[rp] + 1) % Mod) % Mod * inv_2 % Mod) % Mod;
- if (rp != 1) {
- res = (res + 1ll * query(f[0][rp], 1, 0) * (r + 1) % Mod) % Mod;
- }
- }
- return (res + Mod) % Mod;
- }
- void solve() {
- std::cin >> n >> q >> opt, inv_2 = qpow(2, Mod - 2);
- for (int i = 1; i <= n; i++) std::cin >> c[i];
- for (int i = 1; i < n; i++) {
- int u, v;
- std::cin >> u >> v;
- e[u].push_back(v), e[v].push_back(u);
- }
- dfs(1), dfs(1, 1);
- for (int i = 1; i <= n; i++)
- s[0][i] = (s[0][i - 1] + m[dfn[i]]) % Mod,
- s[1][i] = (s[1][i - 1] + 1ll * m[dfn[i]] * m[dfn[i]] % Mod) % Mod,
- s[2][i] = (s[2][i - 1] + nm[dfn[i]]) % Mod,
- s[3][i] = (s[3][i - 1] + 1ll * nm[dfn[i]] * nm[dfn[i]] % Mod) % Mod;
- while (q--) {
- int l, r, a, x = 1ll * opt * ans % n;
- std::cin >> l >> r >> a;
- l = (l + x) % n + 1, r = (r + x) % n + 1, a = (a + x) % n + 1;
- if (l > r) std::swap(l, r);
- ans = ((query(a, r) - query(a, l - 1)) % Mod + Mod) % Mod;
- std::cout << ans << "\n";
- }
- }
- int main() {
- // input(Test), output(Test);
- std::cin.tie(nullptr)->sync_with_stdio(false);
- int _ = 1;
- // std::cin >> _;
- while (_--) solve();
- return 0;
- }
复制代码 [CF1017G] The Tree
pro.
\(n\) 个点的有根树,每个点有黑白两种颜色,初始全为白色。
定义三种操作,每种操作给定 \(x\) :
- 若 \(x\) 为白色,将其染黑并结束操作;否则对 \(x\) 的所有儿子执行该操作(若 \(x\) 为叶子也结束操作);
- 将 \(x\) 及其子树内的点全部染成白色;
- 查询 \(x\) 的颜色。
共 \(q\) 次操作,对于操作三给出答案。
\(n,q\le1e5\)。 \(\mathrm{3s,256MB}\)。
sol.
先考虑没有操作二怎么做。
注意到一个点被染成黑色仅当其某个祖先进行了操作一,且操作的顺序不会影响答案,于是考虑把操作一转为单点加。
但这个条件仅是必要的,而一个点是否被染成黑色还受其根链的后缀有多少个点是白色有关,发现这个信息很难维护。
不妨设白色点的贡献为 \(-1\),发现一个点被能被染成黑色当且仅当其根链上存在一段非负后缀和,于是操作一就转化为了单点修改和根链查询最大后缀和。
加上操作二:直接写成区间覆盖显然不对,因为现在判断一个点的颜色是通过根链,所以子树本身并不影响颜色。考虑查询的是区间后缀和,故初始化为 \(-1\) 的实质是使得白色点的最大后缀和为 \(-1\),于是将整棵子树初始化为 \(-1\) 后,使得子树的根的最大后缀和为 \(-1\) 即可将其实现子树的初始化。
cod.
- #include <bits/stdc++.h>
- #define file(name, suf) ""#name"."#suf""
- #define input(name) freopen(file(name, in), "r", stdin)
- #define output(name) freopen(file(name, out), "w", stdout)
- #define map(type, x) static_cast<type>(x)
- typedef unsigned long long ull;
- constexpr int N = 2e5 + 1, B = 501;
- int n, m, b, cnt, pre[B][B], belong[N];
- ull a[N], tag[B], sum[B];
- struct Tree {
- std::vector<int> e[N];
- int idx, fa[N], dep[N], siz[N], son[N], top[N], num[N], dfn[N];
- void dfs(int u) {
- dep[u] = dep[fa[u]] + 1, siz[u] = 1;
- for (const int& v : e[u])
- if (v != fa[u]) {
- fa[v] = u, dfs(v), siz[u] += siz[v];
- if (siz[v] > siz[son[u]]) son[u] = v;
- }
- }
- void dfs(int u, int tp) {
- top[u] = tp, dfn[num[u] = ++idx] = u;
- if (son[u]) dfs(son[u], tp);
- for (const int& v : e[u])
- if (v != fa[u] && v != son[u])
- dfs(v, v);
- }
- void init() {
- for (int i = 1; i < n; i++) {
- int u, v;
- std::cin >> u >> v;
- e[u].push_back(v), e[v].push_back(u);
- }
- dfs(1), dfs(1, 1);
- }
- } T1, T2;
- void add(int l, int r, ull x) {
- int L = belong[l], R = belong[r];
- if (L == R) {
- for (int i = l, j; i <= r; i++) {
- j = T2.num[T1.dfn[i]];
- a[T2.dfn[j]] += x, sum[belong[j]] += x;
- }
- return;
- }
- for (int i = l, j; belong[i] == L; i++) {
- j = T2.num[T1.dfn[i]];
- a[T2.dfn[j]] += x, sum[belong[j]] += x;
- }
- for (int i = L + 1; i < R; i++) tag[i] += x;
- for (int i = r, j; belong[i] == R; i--) {
- j = T2.num[T1.dfn[i]];
- a[T2.dfn[j]] += x, sum[belong[j]] += x;
- }
- }
- void Add(int u, int v, ull k) {
- int x = u, y = v;
- int *dep = T1.dep, *top = T1.top, *fa = T1.fa, *num = T1.num;
- while (top[u] != top[v]) {
- if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
- add(num[top[u]], num[u], k), u = fa[top[u]];
- }
- if (dep[u] > dep[v]) std::swap(u, v);
- add(num[u], num[v], k);
- int l = dep[u] < dep[v] ? u : v;
- }
- ull query(int l, int r) {
- ull res = 0;
- int L = belong[l], R = belong[r];
- if (L == R) {
- for (int i = l; i <= r; i++) res += a[T2.dfn[i]] + tag[belong[T1.num[T2.dfn[i]]]];
- return res;
- }
- for (int i = l; belong[i] == L; i++) res += a[T2.dfn[i]] + tag[belong[T1.num[T2.dfn[i]]]];
- for (int i = L + 1; i < R; i++) res += sum[i];
- if (R > L + 1) for (int i = 1; i <= cnt; i++) res += tag[i] * (pre[i][R - 1] - pre[i][L]);
- for (int i = r; belong[i] == R; i--) res += a[T2.dfn[i]] + tag[belong[T1.num[T2.dfn[i]]]];
- return res;
- }
- ull Query(int u, int v) {
- ull res = 0;
- int *dep = T2.dep, *top = T2.top, *fa = T2.fa, *num = T2.num;
- while (top[u] != top[v]) {
- if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
- res += query(num[top[u]], num[u]), u = fa[top[u]];
- }
- if (dep[u] > dep[v]) std::swap(u, v);
- return res + query(num[u], num[v]);
- }
- void solve() {
- std::cin >> n >> m, b = map(int, sqrt(n));
- for (int i = 1; i <= n; i++) std::cin >> a[i], belong[i] = (i - 1) / b + 1;
- T1.init(), T2.init(), cnt = belong[n];
- for (int i = 1; i <= n; i++) sum[belong[i]] += a[T2.dfn[i]], pre[belong[T1.num[i]]][belong[T2.num[i]]]++;
- for (int i = 1; i <= cnt; i++) for (int j = 1; j <= cnt; j++) pre[i][j] += pre[i][j - 1];
- while (m--) {
- int x, y;
- ull k;
- std::cin >> x >> y >> k;
- Add(x, y, k), std::cout << Query(x, y) << "\n";
- }
- }
- int main() {
- // input(Test), output(Test);
- std::cin.tie(nullptr)->sync_with_stdio(false);
- int _ = 1;
- // std::cin >> _;
- while (_--) solve();
- return 0;
- }
复制代码 树上启发式合并 (dsu on tree)
依旧像重剖一样定义重儿子,每个点在统计答案时先继承重儿子答案,再遍历所有轻儿子及其子树中的点统计答案,这样做复杂度是 \(\mathcal{O}(n\log n)\) 的。
证明:考虑每个点被遍历到当且仅当它的某个祖先被作为轻儿子统计,故每个点被遍历的次数即为其根链上的轻边个数。而重剖的性质告诉我们:每个点的根链上最多只有 \(\mathcal{O}(\log n)\) 条轻边,故总复杂度 \(\mathcal{O}(n\log n)\)。证毕。
实现时对于每个点,先统计轻儿子答案,然后清空对父亲答案的影响,再统计重儿子答案并保留影响,最后再统计一遍轻儿子影响即可。
所以树上启发式合并常被用于解决某些可离线的树上问题。
[CF1709E] XOR Tree
pro.
\(n\) 个点的树,点有点权。
定义一棵树是好的,当且仅当其不存在一条简单路径上点权的异或和为 \(0\)。
你可以修改任意点的点权为任意正整数,求使这棵树变好的最小操作次数。
\(n\le2e5\)。 \(\mathrm{3s,250MB}\)。
sol.
首先注意到一旦我们对某个点进行修改,我们就可以使所有经过这个点的最短路径的异或和不为 \(0\) (一种方案将其修改为某个极大的 \(2^k\) 的形式)。于是一旦某个点被进行了修改,就可以删去它及它的子树。
一个常用的Trick:树上路径的点权广义和 \(dist(u,v)=dis_u+dis_v-2dis_{\mathrm{lca}(u,v)}+a_{\mathrm{lca}(u,v)}\),其中 \(dis_u\) 表示 \(u\) 到根的点权广义和。
由于 \(\bigoplus\) 具有自反性,所以 \(dist(u,v)=dis_u\bigoplus dis_v\bigoplus a_{\mathrm{lca}(u,v)}\)。
于是我们用 std::set 维护子树内的 \(dis_u\) 集合,对于 \(u\) 的一棵子树,先遍历子树集合,统计当前 \(u\) 的集合中是否存在 \(dis_v\bigoplus a_u\),若存在就把 \(a_u\) 修改并最后清空 \(u\) 集合,否则就把子树集合合并到 \(u\) 集合上。
使用启发式合并即可做到 \(\mathcal{O}(n\log^2 n)\)。
cod.
- #include <bits/stdc++.h>
- #define file(name, suf) ""#name"."#suf""
- #define input(name) freopen(file(name, in), "r", stdin)
- #define output(name) freopen(file(name, out), "w", stdout)
- constexpr int N = 1e5 + 10;
- int n, q, idx, fa[N], siz[N], son[N], top[N], num[N];
- std::vector<int> e[N];
- std::string ans[2] = {"white\n", "black\n"};
- struct Node {
- int sum, suf, len;
- bool cvr, empty;
- Node operator + (const Node& b) {
- if (empty & b.empty) return {0, 0, 0, false, true};
- if (empty) return b;
- else if (b.empty) return *this;
- Node res{};
- res.sum = sum + b.sum, res.suf = std::max(b.suf, suf + b.sum), res.len = len + b.len;
- return res;
- }
- };
- struct Seg_Tree {
- Node t[N << 2];
- #define ls (u << 1)
- #define rs (u << 1 | 1)
- #define mid ((l + r) >> 1)
- void build(int u, int l, int r) {
- t[u] = {-(r - l + 1), -1, r - l + 1, false, false};
- if (l == r) return;
- build(ls, l, mid), build(rs, mid + 1, r);
- }
- void add(int u, int x) {
- t[u].sum += x, t[u].suf += x;
- }
- void cover(int u) {
- t[u].sum = -t[u].len, t[u].suf = -1, t[u].cvr = true;
- }
- void down(int u) {
- if (t[u].cvr) cover(ls), cover(rs), t[u].cvr = false;
- }
- void add(int u, int l, int r, int k, int x) {
- if (l == r) return add(u, x), void();
- down(u);
- if (k <= mid) add(ls, l, mid, k, x);
- else add(rs, mid + 1, r, k, x);
- t[u] = t[ls] + t[rs];
- }
- void cover(int u, int l, int r, int ql, int qr) {
- if (l > qr || r < ql) return;
- if (l >= ql && r <= qr) return cover(u);
- down(u), cover(ls, l, mid, ql, qr), cover(rs, mid + 1, r, ql, qr), t[u] = t[ls] + t[rs];
- }
- Node query(int u, int l, int r, int ql, int qr) {
- if (l > qr || r < ql) return {0, 0, 0, false, true};
- if (l >= ql && r <= qr) return t[u];
- down(u);
- return query(ls, l, mid, ql, qr) + query(rs, mid + 1, r, ql, qr);
- }
- } T;
- void dfs(int u) {
- siz[u] = 1;
- for (const int& v : e[u])
- if (v != fa[u]) {
- fa[v] = u, dfs(v), siz[u] += siz[v];
- if (siz[v] > siz[son[u]]) son[u] = v;
- }
- }
- void dfs(int u, int tp) {
- top[u] = tp, num[u] = ++idx;
- if (son[u]) dfs(son[u], tp);
- for (const int& v : e[u]) if (v != fa[u] && v != son[u]) dfs(v, v);
- }
- void add(int u, int x) { T.add(1, 1, n, num[u], x); }
- Node query(int u) {
- Node res = {0, 0, 0, false, true};
- while (fa[top[u]]) res = T.query(1, 1, n, num[top[u]], num[u]) + res, u = fa[top[u]];
- res = T.query(1, 1, n, 1, num[u]) + res;
- return res;
- }
- void cover(int u) {
- T.cover(1, 1, n, num[u], num[u] + siz[u] - 1);
- Node res = query(u);
- if (res.suf < 0) return;
- T.add(1, 1, n, num[u], -res.suf - 1);
- }
- void solve() {
- std::cin >> n >> q;
- for (int i = 2; i <= n; i++) {
- int x;
- std::cin >> x;
- e[i].push_back(x), e[x].push_back(i);
- }
- dfs(1), dfs(1, 1), T.build(1, 1, n);
- // for (int i = 1; i <= n; i++) std::cout << T.query(1, 1, n, num[i], num[i]).sum << " ";
- // std::cout << "\n";
- while (q--) {
- int op, x;
- std::cin >> op >> x;
- if (op == 1) add(x, 1);
- else if (op == 2) cover(x);
- else {
- std::cout << ans[query(x).suf >= 0];
- // Node res = query(x);
- // std::cout << res.sum << " " << res.suf << "\n";
- }
- // for (int i = 1; i <= n; i++) std::cout << i << " " << T.query(1, 1, n, num[i], num[i]).sum << " " << T.query(1, 1, n, num[i], num[i]).suf << "\n";
- // std::cout << "\n";
- }
- }
- int main() {
- // input(Test), output(Test);
- int _ = 1;
- // std::cin >> _;
- while (_--) solve();
- return 0;
- }
复制代码 [CF600E] Lomsat gelral
pro.
\(n\) 个点的有根树,每个点有一种颜色,对于每个点求出其子树中出现次数最多的颜色的编号之和。
\(n\le1e5\)。 \(\mathrm{2s,256MB}\)。
sol.
全局开一个桶,维护子树中每个颜色出现了多少次,同时统计答案,加点是容易的,于是树上启发式合并即可。
复杂度 \(\mathcal{O}(n\log n)\)。
cod.
- // dep[u] : u的深度
- // fa[u] :u的直接父亲
- // siz[u] : 以 u 的子树大小
- // son[u] : u的重儿子
- // well[u] : u子树内的最大深度
- // top[u] : u所在长链的深度最小点
- // len[u] : u所在长链的深度最大点到u的距离(len[top[u]]即为长链长度)
- void dfs(int u) {
- for (int i = 1; i <= 20; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
- well[u] = dep[u] = dep[fa[u][0]] + 1;
- for (const int& v : e[u])
- if (v != fa[u][0]) {
- dfs(v), well[u] = std::max(well[u], well[v]);
- if (well[v] > well[son[u]]) son[u] = v;
- }
- }
- void dfs(int u, int tp) {
- top[u] = tp, len[u] = well[u] - dep[tp] + 1;
- if (son[u]) dfs(son[u], tp);
- for (const int& v : e[u])
- if (v != fa[u][0] && v != son[u])
- dfs(v, v);
- }
复制代码 [Atcoder-Code Festival 2017-Final-J] Tree MST
pro.
有一张 \(n\) 个点的完全图。给定一棵 \(n\) 个点的树,点有点权,边有边权。
完全图上 \(u,v\) 两点之间的边权为 \(w_u+w_v+\mathrm{dis}(u,v)\),其中 \(w_u\) 为 \(u\) 的点权,\(\mathrm{dis}(u,v)\) 为树上两点简单路径上的边权和。
求完全图的最小生成树边权和。
\(n\le2e5\)。\(\mathrm{5s,256MB}\)。
sol.
定理:对于(一般)完全图最小生成树问题,可以先任选一个边集跑一遍最小生成树,把选中的边保留下来,再与其余边跑一遍最小生成树即为答案。
推论(Trick):对于原图的边集 \(E\),若有 \(\bigcup_{i=1}^kE_i=E\),则先对 \(E_i\) 分别求得最小生成树,对被选中的边构成的集合求出的最小生成树等于直接对 \(E\) 求得的最小生成树。
观察到两点间的距离仍然和路径有关,考虑点分治。
根据推论,对于每一个分治中心,只需要先求出其在点分树上的子树内点的最小生成树,最后对所有保留的边做一遍 Kruskal 即可。由于每个点只会在其点分树的祖先上连一条边,故总边数 \(\mathcal{O}(n\log n)\),最后 Kruskal 复杂度 \(\mathcal{O}(n\log^2n)\)。
于是问题变为如何快速对一个分治中心求出最小生成树。记 \(dis_u\) 为 \(u\) 到当前分治中心的距离,则完全图上 \((u,v)\) 的边权即为 \(w_u+w_v+dis_u+dis_v\)。贪心的想,每个点向 \(w_u+dis_u\) 最小的点连边即为最小生成树。对于 \(u,v\) 在同一棵子树内的情况,由于一定比全局答案劣,所以也不需要排除。点分治连边部分复杂度 \(\mathcal{O}(n\log n)\)。
总复杂度 \(\mathcal{O}(n\log^2n)\)。
cod.
- #include <bits/stdc++.h>
- typedef long long ll;
- typedef unsigned int ui;
- ui s;
- inline ui get(ui x) {
- x ^= x << 13;
- x ^= x >> 17;
- x ^= x << 5;
- return s = x;
- }
- const int N = 5e5 + 10;
- int n, q, root, fa[N][21], dep[N], well[N], son[N], top[N], len[N], ans;
- std::vector<int> e[N], up[N], down[N];
- ll output;
- void dfs(int u) {
- for (int i = 1; i <= 20; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
- well[u] = dep[u] = dep[fa[u][0]] + 1;
- for (const int& v : e[u])
- if (v != fa[u][0]) {
- dfs(v), well[u] = std::max(well[u], well[v]);
- if (well[v] > well[son[u]]) son[u] = v;
- }
- }
- void dfs(int u, int tp) {
- top[u] = tp, len[u] = well[u] - dep[tp] + 1;
- if (u == tp) for (int i = 1, anc = fa[u][0], des = son[u]; i <= len[u]; i++, anc = fa[anc][0], des = son[des]) up[u].push_back(anc), down[u].push_back(des);
- if (son[u]) dfs(son[u], tp);
- for (const int& v : e[u])
- if (v != fa[u][0] && v != son[u])
- dfs(v, v);
- }
- void ask(int& x, int& k) {
- x = (get(s) ^ ans) % n + 1;
- k = (get(s) ^ ans) % dep[x];
- }
- int find(int x, int k) {
- if (!k) return x;
- int t = static_cast<int>(log2(k));
- x = fa[x][t], k -= (1 << t) + dep[x] - dep[top[x]], x = top[x];
- return k == 0 ? x : (k > 0 ? up[x][k - 1] : down[x][-k - 1]);
- }
- void solve() {
- std::cin >> n >> q >> s;
- for (int i = 1; i <= n; i++) std::cin >> fa[i][0], root = fa[i][0] == 0 ? i : root, e[i].push_back(fa[i][0]), e[fa[i][0]].push_back(i);
- dfs(root), dfs(root, root);
- for (int i = 1, x, k; i <= q; i++) ask(x, k), ans = find(x, k), output ^= (ll)i * ans;
- std::cout << output << "\n";
- }
- int main() {
- int _ = 1;
- while (_--) solve();
- return 0;
- }
复制代码 [QOJ7855] 不跳棋
pro.
\(n\) 个点的树,每个点初始均有一个棋子。
共操作 \(n-2\) 次,每次拿走一个棋子。
求出每次操作后任意两个不同棋子之间的最短距离及点对数。
强制在线。
\(n\le5e5\)。\(\mathrm{5s,512MB}\)。
sol.
对于每一个状态显然可以用点分治 \(\mathcal{O}(n\log n)\) 完成,问题在于如何修改。
考虑建出点分树,显然删去某个点只会影响其 \(\mathcal{O}(\log n)\) 个祖先的路径信息。
于是对每个分治中心维护一个桶 \(cnt_x\) 表示到该分治中心的距离为 \(x\) 的点的数量,并维护最小值和次小值指针 \(min,cmin\),再对全局开一个桶 \(ans_x\) 表示距离为 \(x\) 的点对数,并维护全局最小值指针。
容易发现删点答案单调不降,暴力维护指针均摊 \(\mathcal{O}(1)\) 。
总的时空复杂度均为 \(\mathcal{O}(n\log n)\) 。
cod.
- #include <bits/stdc++.h>
- #define file(name, suf) ""#name"."#suf""
- #define input(name) freopen(file(name, in), "r", stdin)
- #define output(name) freopen(file(name, out), "w", stdout)
- constexpr int N = 1e6 + 10;
- int n, len[N], son[N], b[N], *g[N], ans[N];
- int *now = b;
- std::vector<int> e[N];
- void dfs(int u, int f) {
- for (const int& v : e[u])
- if (v != f) {
- dfs(v, u);
- if (len[v] > len[son[u]]) son[u] = v;
- }
- len[u] = len[son[u]] + 1;
- }
- void dp(int u, int f) {
- g[u][0] = 1;
- if (son[u]) g[son[u]] = g[u] + 1, dp(son[u], u), ans[u] = ans[son[u]] + 1;
- for (const int& v : e[u])
- if (v != f && v != son[u]) {
- g[v] = now, now += len[v], dp(v, u);
- for (int i = 1; i <= len[v]; i++) {
- g[u][i] += g[v][i - 1];
- if (g[u][i] > g[u][ans[u]]) ans[u] = i;
- else if (g[u][i] == g[u][ans[u]] && i < ans[u]) ans[u] = i;
- }
- }
- if (g[u][ans[u]] == 1) ans[u] = 0;
- }
- void solve() {
- std::cin >> n;
- for (int i = 1; i < n; i++) {
- int u, v;
- std::cin >> u >> v;
- e[u].push_back(v), e[v].push_back(u);
- }
- dfs(1, 0), g[1] = now, now += len[1], dp(1, 0);
- for (int i = 1; i <= n; i++) std::cout << ans[i] << "\n";
- }
- int main() {
- // input(Test), output(Test);
- std::cin.tie(nullptr)->sync_with_stdio(false);
- int _ = 1;
- // std::cin >> _;
- while (_--) solve();
- return 0;
- }
复制代码 来源:程序园用户自行投稿发布,如果侵权,请联系站长删除
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作! |