2025北京集训Day1&Day3
树链剖分重剖
对于一棵 \(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的深度
// fa ：u的直接父亲
// siz : 以 u 的子树大小
// son : u的重儿子
// top : u所在重链的深度最小的点
void dfs(int u) {
dep = dep] + 1, siz = 1;
for (const int& v : e)
if (v != fa) {
fa = u, dfs(v), siz += siz;
if (siz > siz]) son = v;
}
}
void dfs(int u, int tp) {
top = tp, dfn = ++idx] = u;
if (son) dfs(son, tp);
for (const int& v : e)
if (v != fa && v != son)
dfs(v, v);
} 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\)，我们让 \(\) 的每个点到根链做一遍赋值，累加权值，最后统计 \(z\) 的根链和即为答案。
于是我们把不容易维护的 \(\mathrm{lca}\) 转化为了容易维护的根链加和根链查询和，树剖线段树很容易维护。
但这导致询问之间可能有相互影响，所以每次查询要清空线段树，复杂度难以接受。
把询问拆成 \(-\)，然后离线询问，从 \(\) 依次修改，每到一个点就在对应的询问上统计权值，复杂度 \(\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, dep, siz, son, top, num;
std::vector<int> e;
struct Query { int r, z, ans, id; } q;
struct Seg_Tree {
struct Node { int len, sum, add; } t;
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid ((l + r) >> 1)
void up(int u) { t.sum = (t.sum + t.sum) % Mod; }
void build(int u, int l, int r) {
t = {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.sum = (t.sum + 1ll * x * t.len % Mod) % Mod;
t.add = (t.add + x) % Mod;
}
void down(int u) {
if (t.add) add(ls, t.add), add(rs, t.add), t.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.sum;
down(u);
return (query(ls, l, mid, ql, qr) + query(rs, mid + 1, r, ql, qr)) % Mod;
}
} T;
void dfs(int u) {
dep = dep] + 1, siz = 1;
for (const int& v : e)
if (v != fa) {
fa = u, dfs(v), siz += siz;
if (siz > siz]) son = v;
}
}
void dfs(int u, int tp) {
top = tp, num = ++idx;
if (son) dfs(son, tp);
for (const int& v : e)
if (v != fa && v != son)
dfs(v, v);
}
void add(int u, int v, int x) {
while (top != top) {
if (dep] < dep]) std::swap(u, v);
T.add(1, 1, n, num], num, 1);
u = fa];
}
if (dep > dep) std::swap(u, v);
T.add(1, 1, n, num, num, 1);
}
int query(int u, int v) {
int res = 0;
while (top != top) {
if (dep] < dep]) std::swap(u, v);
res = (res + T.query(1, 1, n, num], num)) % Mod;
u = fa];
}
if (dep > dep) std::swap(u, v);
return (res + T.query(1, 1, n, num, num)) % 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.push_back(f), e.push_back(i);
}
for (int i = 1; i <= m; i++) {
int l, r, z;
std::cin >> l >> r >> z, ++l, ++r, ++z;
q.r = l - 1, q.z = z;
q.r = r, q.z = z;
q.id = q.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.r < 1) now++;
for (int i = 1; i <= n; i++) {
add(1, i, 1);
while (now <= m << 1 && q.r == i)
q.ans = query(1, q.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.ans - q.ans) % Mod + Mod) % Mod << "\n";
}
int main() {
// input(Test), output(Test);
int _ = 1;
// std::cin >> _;
while (_--) solve();
return 0;
} 简单的树
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, dep, son, siz, top, dfn, num;
std::vector<int> e;
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;
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid ((l + r) >> 1)
void build(int u, int l, int r) {
t.len = r - l + 1, t.ans = 0;
if (l == r) return t.l = t.r = l, void();
build(ls, l, mid), build(rs, mid + 1, r), t = t + t;
}
void cover(int u, int x) {
t.l = t.r = t.cvr = x;
t.ans = t.len - 1;
}
void down(int u) {
if (t.cvr) cover(ls, t.cvr), cover(rs, t.cvr), t.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 = t + t;
}
int query(int u, int l, int r, int k) {
if (l == r) return t.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;
down(u);
return query(ls, l, mid, ql, qr) + query(rs, mid + 1, r, ql, qr);
}
} T;
void dfs(int u) {
dep = dep] + 1, siz = 1;
for (const int& v : e)
if (v != fa) {
fa = u, dfs(v), siz += siz;
if (siz > siz]) son = v;
}
}
void dfs(int u, int tp) {
dfn = ++idx] = u, top = tp;
if (son) dfs(son, tp);
for (const int& v : e)
if (v != fa && v != son)
dfs(v, v);
}
void cover(int u, int v, int x) {
while (top != top) {
if (dep] < dep]) std::swap(u, v);
T.cover(1, 1, n, num], num, x);
u = fa];
}
if (dep > dep) std::swap(u, v);
T.cover(1, 1, n, num, num, x);
}
int query(int u, int v) {
Node L{}, R{}, res{};
while (top != top) {
if (dep] > dep]) {
res = T.query(1, 1, n, num], num);
std::swap(res.l, res.r);
L = L + res;
u = fa];
} else {
res = T.query(1, 1, n, num], num);
R = res + R;
v = fa];
}
}
if (dep < dep) {
res = T.query(1, 1, n, num, num);
res = L + res + R;
} else {
res = T.query(1, 1, n, num, num);
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.clear(), son = 0;
for (int i = 1; i < n; i++) {
int u, v;
std::cin >> u >> v;
e.push_back(v), e.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;
} 树上简单求和
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, inv_2;
int idx, f, dep, siz, son, top, dfn, num;
int m, nm, dis, s, ans;
std::vector<int> e;
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 = c, dep = dep] + 1, siz = 1;
for (int i = 1; (1 << i) <= dep; i++) f = f];
for (const int& v : e)
if (v != f) {
f = u, dfs(v), siz += siz;
if (siz > siz]) son = v;
if (m > m) nm = m, m = m;
else if (m > nm) nm = m;
if (nm > nm) nm = nm;
}
}
void dfs(int u, int tp) {
top = tp, dfn = ++idx] = u, dis = (dis] + m) % Mod;
if (son) dfs(son, tp);
for (const int& v : e)
if (v != f && v != son)
dfs(v, v);
}
int query(int u, int v, int k) {
int res = 0;
while (top != top) {
if (dep] < dep]) std::swap(u, v);
res = (res + s] - s] - 1]) % Mod;
u = f];
}
if (dep > dep) std::swap(u, v);
return (res + s] - s - 1]) % Mod;
}
int query(int a, int r) {
int p = a, res = 1ll * (s - dis) * (r + 1) % Mod;
if (m == c) {
for (int i = std::__lg(dep); ~i; i--) if (f && m] == c) p = f;
if (nm >= r) {
res = (res + 1ll * query(a, p, 2) * (r + 1) % Mod) % Mod;
} else {
int lp = a;
for (int i = std::__lg(dep - dep + 1); ~i; i--) {
if (dep] >= dep && nm] < r)
lp = f;
}
res = (res + (1ll * (query(a, lp, 3) + query(a, lp, 2)) % Mod + 1ll * r * (r + 1) % Mod * (dep - dep + 1) % Mod) % Mod * inv_2 % Mod) % Mod;
if (lp != p) {
res = (res + 1ll * query(f, p, 2) * (r + 1) % Mod) % Mod;
}
}
if (p == 1) return (res + Mod) % Mod;
p = f;
}
if (m >= r) {
res = (res + 1ll * query(p, 1, 0) * (r + 1) % Mod) % Mod;
} else {
int rp = p;
for (int i = std::__lg(dep - 1); ~i; i--) {
if (f && m] < r)
rp = f;
}
res = (res + (1ll * (query(p, rp, 1) + query(p, rp, 0)) % Mod + 1ll * r * (r + 1) % Mod * (dep - dep + 1) % Mod) % Mod * inv_2 % Mod) % Mod;
if (rp != 1) {
res = (res + 1ll * query(f, 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;
for (int i = 1; i < n; i++) {
int u, v;
std::cin >> u >> v;
e.push_back(v), e.push_back(u);
}
dfs(1), dfs(1, 1);
for (int i = 1; i <= n; i++)
s = (s + m]) % Mod,
s = (s + 1ll * m] * m] % Mod) % Mod,
s = (s + nm]) % Mod,
s = (s + 1ll * nm] * nm] % 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;
} 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, belong;
ull a, tag, sum;
struct Tree {
std::vector<int> e;
int idx, fa, dep, siz, son, top, num, dfn;
void dfs(int u) {
dep = dep] + 1, siz = 1;
for (const int& v : e)
if (v != fa) {
fa = u, dfs(v), siz += siz;
if (siz > siz]) son = v;
}
}
void dfs(int u, int tp) {
top = tp, dfn = ++idx] = u;
if (son) dfs(son, tp);
for (const int& v : e)
if (v != fa && v != son)
dfs(v, v);
}
void init() {
for (int i = 1; i < n; i++) {
int u, v;
std::cin >> u >> v;
e.push_back(v), e.push_back(u);
}
dfs(1), dfs(1, 1);
}
} T1, T2;
void add(int l, int r, ull x) {
int L = belong, R = belong;
if (L == R) {
for (int i = l, j; i <= r; i++) {
j = T2.num];
a] += x, sum] += x;
}
return;
}
for (int i = l, j; belong == L; i++) {
j = T2.num];
a] += x, sum] += x;
}
for (int i = L + 1; i < R; i++) tag += x;
for (int i = r, j; belong == R; i--) {
j = T2.num];
a] += x, sum] += 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 != top) {
if (dep] < dep]) std::swap(u, v);
add(num], num, k), u = fa];
}
if (dep > dep) std::swap(u, v);
add(num, num, k);
int l = dep < dep ? u : v;
}
ull query(int l, int r) {
ull res = 0;
int L = belong, R = belong;
if (L == R) {
for (int i = l; i <= r; i++) res += a] + tag]]];
return res;
}
for (int i = l; belong == L; i++) res += a] + tag]]];
for (int i = L + 1; i < R; i++) res += sum;
if (R > L + 1) for (int i = 1; i <= cnt; i++) res += tag * (pre - pre);
for (int i = r; belong == R; i--) res += a] + tag]]];
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 != top) {
if (dep] < dep]) std::swap(u, v);
res += query(num], num), u = fa];
}
if (dep > dep) std::swap(u, v);
return res + query(num, num);
}
void solve() {
std::cin >> n >> m, b = map(int, sqrt(n));
for (int i = 1; i <= n; i++) std::cin >> a, belong = (i - 1) / b + 1;
T1.init(), T2.init(), cnt = belong;
for (int i = 1; i <= n; i++) sum] += a], pre]]]]++;
for (int i = 1; i <= cnt; i++) for (int j = 1; j <= cnt; j++) pre += pre;
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)\)。证毕。
实现时对于每个点，先统计轻儿子答案，然后清空对父亲答案的影响，再统计重儿子答案并保留影响，最后再统计一遍轻儿子影响即可。
所以树上启发式合并常被用于解决某些可离线的树上问题。
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, siz, son, top, num;
std::vector<int> e;
std::string ans = {"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;
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid ((l + r) >> 1)
void build(int u, int l, int r) {
t = {-(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.sum += x, t.suf += x;
}
void cover(int u) {
t.sum = -t.len, t.suf = -1, t.cvr = true;
}
void down(int u) {
if (t.cvr) cover(ls), cover(rs), t.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 = t + t;
}
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 = t + t;
}
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;
down(u);
return query(ls, l, mid, ql, qr) + query(rs, mid + 1, r, ql, qr);
}
} T;
void dfs(int u) {
siz = 1;
for (const int& v : e)
if (v != fa) {
fa = u, dfs(v), siz += siz;
if (siz > siz]) son = v;
}
}
void dfs(int u, int tp) {
top = tp, num = ++idx;
if (son) dfs(son, tp);
for (const int& v : e) if (v != fa && v != son) dfs(v, v);
}
void add(int u, int x) { T.add(1, 1, n, num, x); }
Node query(int u) {
Node res = {0, 0, 0, false, true};
while (fa]) res = T.query(1, 1, n, num], num) + res, u = fa];
res = T.query(1, 1, n, 1, num) + res;
return res;
}
void cover(int u) {
T.cover(1, 1, n, num, num + siz - 1);
Node res = query(u);
if (res.suf < 0) return;
T.add(1, 1, n, num, -res.suf - 1);
}
void solve() {
std::cin >> n >> q;
for (int i = 2; i <= n; i++) {
int x;
std::cin >> x;
e.push_back(x), e.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, num).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;
// 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, num).sum << " " << T.query(1, 1, n, num, num).suf << "\n";
// std::cout << "\n";
}
}
int main() {
// input(Test), output(Test);
int _ = 1;
// std::cin >> _;
while (_--) solve();
return 0;
} Lomsat gelral
pro.
\(n\) 个点的有根树，每个点有一种颜色，对于每个点求出其子树中出现次数最多的颜色的编号之和。
\(n\le1e5\)。 \(\mathrm{2s,256MB}\)。
sol.
全局开一个桶，维护子树中每个颜色出现了多少次，同时统计答案，加点是容易的，于是树上启发式合并即可。
复杂度 \(\mathcal{O}(n\log n)\)。
cod.
// dep : u的深度
// fa ：u的直接父亲
// siz : 以 u 的子树大小
// son : u的重儿子
// well : u子树内的最大深度
// top : u所在长链的深度最小点
// len : u所在长链的深度最大点到u的距离（len]即为长链长度）
void dfs(int u) {
for (int i = 1; i <= 20; i++) fa = fa];
well = dep = dep] + 1;
for (const int& v : e)
if (v != fa) {
dfs(v), well = std::max(well, well);
if (well > well]) son = v;
}
}
void dfs(int u, int tp) {
top = tp, len = well - dep + 1;
if (son) dfs(son, tp);
for (const int& v : e)
if (v != fa && v != son)
dfs(v, v);
} 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, dep, well, son, top, len, ans;
std::vector<int> e, up, down;
ll output;
void dfs(int u) {
for (int i = 1; i <= 20; i++) fa = fa];
well = dep = dep] + 1;
for (const int& v : e)
if (v != fa) {
dfs(v), well = std::max(well, well);
if (well > well]) son = v;
}
}
void dfs(int u, int tp) {
top = tp, len = well - dep + 1;
if (u == tp) for (int i = 1, anc = fa, des = son; i <= len; i++, anc = fa, des = son) up.push_back(anc), down.push_back(des);
if (son) dfs(son, tp);
for (const int& v : e)
if (v != fa && v != son)
dfs(v, v);
}
void ask(int& x, int& k) {
x = (get(s) ^ ans) % n + 1;
k = (get(s) ^ ans) % dep;
}
int find(int x, int k) {
if (!k) return x;
int t = static_cast<int>(log2(k));
x = fa, k -= (1 << t) + dep - dep], x = top;
return k == 0 ? x : (k > 0 ? up : down[-k - 1]);
}
void solve() {
std::cin >> n >> q >> s;
for (int i = 1; i <= n; i++) std::cin >> fa, root = fa == 0 ? i : root, e.push_back(fa), e].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;
} 不跳棋
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, son, b, *g, ans;
int *now = b;
std::vector<int> e;
void dfs(int u, int f) {
for (const int& v : e)
if (v != f) {
dfs(v, u);
if (len > len]) son = v;
}
len = len] + 1;
}
void dp(int u, int f) {
g = 1;
if (son) g] = g + 1, dp(son, u), ans = ans] + 1;
for (const int& v : e)
if (v != f && v != son) {
g = now, now += len, dp(v, u);
for (int i = 1; i <= len; i++) {
g += g;
if (g > g]) ans = i;
else if (g == g] && i < ans) ans = i;
}
}
if (g] == 1) ans = 0;
}
void solve() {
std::cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
std::cin >> u >> v;
e.push_back(v), e.push_back(u);
}
dfs(1, 0), g = now, now += len, dp(1, 0);
for (int i = 1; i <= n; i++) 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;
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]