树链剖分
- ① 将一颗树转化成一个序列
- ② 将树中的每一条路径转化成 $log_n$ 段连续区间
重儿子:对于某个节点而言,节点个数最多的子节点
- 重边:重儿子和其父节点之间的边。
- 重链:由极大的重边构成的路径。
轻儿子:该节点的重儿子以外的节点
- 轻边:轻儿子和其父节点之间的边
每一个点都要在一个重链里
- 重儿子在他父节点的重链里
- 轻儿子在以这个点开头的以下的重链里面
- 叶节点是轻儿子,那么这就是一个单独(特殊)的重链
- 所以所有轻儿子都是一条链的顶点
$dfs$ 的时候按优先遍历重儿子的顺序 创建 $dfs$ 序
- 这样可以让一条重链的编号是连续的
核心结论:树中任意一条路径都可以拆分成 $log_n$ 条重链,每条重链的编号都是连续的,即可拆分成 $log_n$ 个连续区间
如何将一条路径转转化成若干条重链?
- 从两个点最底下的链不断往上爬,每次用比较低的点爬
2568.树链剖分
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long i64;
const int N = 1e5 + 10, M = N * 2;
int n, m;
int h[N], w[N], e[M], ne[M], idx;
int id[N], nw[N], cnt;
int dep[N], sz[N], top[N], fa[N], son[N];
struct Node
{
int l, r;
i64 v, lazy;
}tr[N << 2];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs1(int u)
{
sz[u] = 1;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (dep[j]) continue;
fa[j] = u, dep[j] = dep[u] + 1;
dfs1(j);
sz[u] += sz[j];
if (sz[son[u]] < sz[j]) son[u] = j;
}
}
void dfs2(int u, int tp)
{
id[u] = ++ cnt, nw[cnt] = w[u], top[u] = tp;
if (!son[u]) return ;
dfs2(son[u], tp);
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == fa[u] || j == son[u]) continue;
dfs2(j, j);
}
}
void pushup(int u)
{
tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v;
}
void pushdown(int u)
{
auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
if (root.lazy)
{
left.lazy += root.lazy, left.v += (left.r - left.l + 1) * root.lazy;
right.lazy += root.lazy, right.v += (right.r - right.l + 1) * root.lazy;
root.lazy = 0;
}
}
void build(int u, int l, int r)
{
tr[u] = {l, r, nw[r], 0};
if (l == r) return ;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void update(int u, int l, int r, int k)
{
if (tr[u].l >= l && tr[u].r <= r)
{
tr[u].lazy += k;
tr[u].v += (tr[u].r - tr[u].l + 1) * k;
}
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) update(u << 1, l, r, k);
if (r > mid) update(u << 1 | 1, l, r, k);
pushup(u);
}
}
i64 query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;
pushdown(u);
i64 res = 0;
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) res = query(u << 1, l, r);
if (r > mid) res += query(u << 1 | 1, l, r);
return res;
}
void update_path(int u, int v, int k)
{
while (top[u] != top[v])
{
if (dep[top[u]] < dep[top[v]]) swap(u, v);
update(1, id[top[u]], id[u], k);
u = fa[top[u]];
}
if (dep[u] < dep[v]) swap(u, v);
update(1, id[v], id[u], k);
}
i64 query_path(int u, int v)
{
i64 res = 0;
while (top[u] != top[v])
{
if (dep[top[u]] < dep[top[v]]) swap(u, v);
res += query(1, id[top[u]], id[u]);
u = fa[top[u]];
}
if (dep[u] < dep[v]) swap(u, v);
res += query(1, id[v], id[u]);
return res;
}
void update_tree(int u, int k)
{
update(1, id[u], id[u] + sz[u] - 1, k);
}
i64 query_tree(int u)
{
return query(1, id[u], id[u] + sz[u] - 1);
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
for (int i = 0; i < n - 1; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
dep[1] = 1;
dfs1(1), dfs2(1, 1);
build(1, 1, n);
scanf("%d", &m);
while (m -- )
{
int t, u, v, k;
scanf("%d%d", &t, &u);
if (t == 1)
{
scanf("%d%d", &v, &k);
update_path(u, v, k);
}
else if (t == 2)
{
scanf("%d", &k);
update_tree(u, k);
}
else if (t == 3)
{
scanf("%d", &v);
printf("%lld\n", query_path(u, v));
}
else printf("%lld\n", query_tree(u));
}
return 0;
}
一看到一百多行的代码就怕QwQ
一直想学树链剖分,但是一直没学(因为看了一眼发现看不懂)
真的要好好补补了hh
不难的,O(∩_∩)O
嗯嗯,在学了hh
挺好玩的,就是代码老长