题目传送门:#8. 「模板」树链剖分、
前置知识
-
重链：重链（Heavy Path）是指树链剖分中的一条主要的路径，该路径上的节点数量较多，相邻节点之间的距离较近。轻链（Light Path）是指树链剖分中的其他路径，相邻节点之间的距离较远。
-
LCA：最近公共祖先
分析
上树状数组
首先，我们需要定义一个数组vals来存储每个节点的权值。然后，我们可以使用一个数组tree来表示树状数组，数组的下标表示节点的编号。对于节点i，其在tree数组中的下标为i，其父节点在tree数组中的下标为i+(i&-i)
然后只需要实现以下几个操作：
换根：将树的根节点设置为新根节点x。我们可以将所有节点的权值都减去vals[x]，然后再将vals[x]加到所有节点的权值中即可。
修改路径权值：给定两个节点u和v，将节点u到节点v的路径上的所有节点权值增加一个给定的值x。我们可以先将节点u的权值增加x，然后再将节点v的权值减去x。最后将tree数组中节点u到节点v的路径上的节点的值都增加x。
修改子树权值：给定一个节点x，将以节点x为根的子树内的所有节点权值增加一个给定的值y。我们可以将节点x的权值增加y，然后将tree数组中节点x及其所有子节点的值都增加y。
询问路径：给定两个节点u和v，询问节点u到节点v的路径上所有节点权值的和。我们可以先计算节点v到根节点的权值和，再计算节点u的权值，最后将两者相减即可。
询问子树：给定一个节点x，询问以节点x为根的子树内所有节点权值的和。我们可以直接返回tree数组中节点x及其所有子节点的值的和。
✿✿ヽ(°▽°)ノ✿
等等，还要上代码
Code
10分
#include <cstdio>
#define reg register
int read() {
reg int s = 0, f = 1;
reg char ch;
for (; (ch = getchar()) < '0' || ch > '9'; ch == '-' ? f = -f : 0)
;
for (; ch >= '0' && ch <= '9'; s = (s << 3) + (s << 1) + ch - 48, ch = getchar())
;
return s * f;
}
const int N = 1e5 + 50;
int next[N], to[N], first[N], tag[N << 2], tree[N << 2], val[N], cnt = 0, tot = 0, n, m;
int dfn[N], son[N], size[N], efn[N], dep[N], top[N], fa[N], root, g[N];
inline void push_up(int now) { tree[now] = tree[now << 1] + tree[now << 1 | 1]; }
inline void add(int now, int l, int r, int v) {
tree[now] += (r - l + 1) * v;
tag[now] += v;
}
void push_down(int now, int l, int r) {
if (tag[now]) {
int mid = (l + r) >> 1;
add(now << 1, l, mid, tag[now]);
add(now << 1 | 1, mid + 1, r, tag[now]);
tag[now] = 0;
}
}
void _add(int u, int v) { next[++cnt] = first[u], first[u] = cnt, to[cnt] = v; }
void build(int now, int l, int r) {
if (l == r) {
tree[now] = val[g[l]];
return;
}
int mid = (l + r) >> 1;
build(now << 1, l, mid);
build(now << 1 | 1, mid + 1, r);
push_up(now);
}
void mobify(int now, int l, int r, int L, int R, int v) {
if (L <= l && r <= R) {
add(now, l, r, v);
return;
}
int mid = (l + r) >> 1;
push_down(now, l, r);
if (L <= mid)
mobify(now << 1, l, mid, L, R, v);
if (R > mid)
mobify(now << 1 | 1, mid + 1, r, L, R, v);
push_up(now);
}
int query(int now, int l, int r, int L, int R) {
if (L <= l && r <= R)
return tree[now];
int mid = (l + r) >> 1, ans = 0;
push_down(now, l, r);
if (L <= mid)
ans += query(now << 1, l, mid, L, R);
if (R > mid)
ans += query(now << 1 | 1, mid + 1, r, L, R);
return ans;
}
void dfs0(int now) {
son[now] = 0;
size[now] = 1;
for (reg int i = first[now]; i; i = next[i])
if (!dep[to[i]]) {
fa[to[i]] = now;
dep[to[i]] = dep[now] + 1;
dfs0(to[i]);
size[now] += size[to[i]];
if (!son[now] || size[to[i]] > size[son[now]])
son[now] = to[i];
}
}
void dfs1(int now, int t) {
dfn[now] = ++tot;
top[now] = t;
g[tot] = now;
if (son[now])
dfs1(son[now], t);
for (reg int i = first[now]; i; i = next[i])
if (!dfn[to[i]])
dfs1(to[i], to[i]);
efn[now] = tot;
}
int lca(int u, int v) {
while (top[u] != top[v]) (dep[top[u]] > dep[top[v]]) ? u = fa[top[u]] : v = fa[top[v]];
return (dep[u] < dep[v]) ? u : v;
}
void addpath(int u, int v, int k) {
while (top[u] != top[v])
(dep[top[u]] > dep[top[v]]) ? (mobify(1, 1, n, dfn[top[u]], dfn[u], k), u = fa[top[u]])
: (mobify(1, 1, n, dfn[top[v]], dfn[v], k), v = fa[top[v]]);
(dep[u] < dep[v]) ? mobify(1, 1, n, dfn[u], dfn[v], k) : mobify(1, 1, n, dfn[v], dfn[u], k);
}
void addtree(int u, int k) {
if (u == root) {
mobify(1, 1, n, 1, n, k);
return;
}
int g = lca(u, root);
if (g != u)
mobify(1, 1, n, dfn[u], efn[u], k); // puts("wtf");
else {
// puts("wtm");
if (dfn[root] > 1)
mobify(1, 1, n, 1, dfn[root] - 1, k);
if (efn[root] < n)
mobify(1, 1, n, efn[root] + 1, n, k);
// mobify(1,1,n,1,dfn[u]-1,k);
// mobify(1,1,n,efn[u]+1,n,k);
}
}
void querypath(int u, int v) {
int ans = 0;
while (top[u] != top[v])
if (dep[top[u]] > dep[top[v]])
ans += query(1, 1, n, dfn[top[u]], dfn[u]), u = fa[top[u]];
else
ans += query(1, 1, n, dfn[top[v]], dfn[v]), v = fa[top[v]];
// printf("%d %d %d\n",u,v,ans);
ans += (dep[u] < dep[v]) ? query(1, 1, n, dfn[u], dfn[v]) : query(1, 1, n, dfn[v], dfn[u]);
printf("%d\n", ans);
}
void querytree(int u) {
if (u == root) {
printf("%d\n", tree[1]);
return;
}
int g = lca(u, root);
if (g != u)
printf("%d\n", query(1, 1, n, dfn[u], efn[u]));
else {
int ans = 0;
if (dfn[root] > 1)
ans += query(1, 1, n, 1, dfn[root] - 1);
if (efn[root] < n)
ans += query(1, 1, n, efn[root] + 1, n);
printf("%d\n", ans);
}
}
int main() {
n = read();
root = 1;
for (reg int i = 1; i <= n; i++) val[i] = read();
for (reg int u = 2, v; u <= n; u++) v = read(), _add(v, u);
m = read();
dep[1] = 1;
dfs0(1);
dfs1(1, 1);
build(1, 1, n);
for (reg int i = 1, opt, u, v, k; i <= m; i++) {
opt = read();
if (opt == 1)
root = read();
if (opt == 2)
u = read(), v = read(), k = read(), addpath(u, v, k);
if (opt == 3)
u = read(), k = read(), addtree(u, k);
if (opt == 4)
u = read(), v = read(), querypath(u, v);
if (opt == 5)
u = read(), querytree(u);
}
return 0;
}
100分代码
#include <bits/stdc++.h>
#define INF 0x7fffffff
#define ll long long
using namespace std;
ll read() {
ll k = 1, x = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
k = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - 48, ch = getchar();
return k * x;
}
const int N = 3e5 + 10;
struct EDGE {
ll to, pre;
} edge[N];
ll a[N], size[N], fa[N], dep[N], id[N], w[N], son[N], top[N], head[N];
ll cnt, n, m, r;
//========== 关于换根的操作 =========
inline ll find(ll u, ll v) { //找从u(题目查询点的)到root第一个儿子
while (top[u] != top[v]) {
if (dep[top[u]] > dep[top[v]])
swap(u, v); //保证u的深度更浅
if (fa[top[v]] == u)
return top[v]; //若链头的父亲恰好为u返回链头
v = fa[top[v]]; //不断向上跳
}
if (dep[u] > dep[v])
swap(u, v);
return son[u];
}
inline ll lca(ll u, ll v) {
while (top[u] != top[v]) {
if (dep[top[u]] > dep[top[v]])
swap(u, v);
v = fa[top[v]];
}
return dep[u] >= dep[v] ? v : u;
}
//==================================
//================== 以下为线段树模板 ====================
#define up(x) t[x].sum = t[x << 1].sum + t[x << 1 | 1].sum
struct node {
ll l, r;
ll sum, lazy;
} t[N << 2];
ll len(ll p) { return t[p].r - t[p].l + 1; }
void brush(ll p, ll k) {
t[p].lazy += k;
t[p].sum += len(p) * k;
}
void push_down(ll p) {
brush(p << 1, t[p].lazy);
brush(p << 1 | 1, t[p].lazy);
t[p].lazy = 0;
}
void build(ll p, ll l, ll r) {
t[p].l = l;
t[p].r = r;
if (l == r) {
t[p].sum = w[l];
return;
}
ll mid = l + r >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
up(p);
}
void update(ll p, ll l, ll r, ll k) {
if (t[p].l >= l && t[p].r <= r) {
brush(p, k);
return;
}
push_down(p);
ll mid = t[p].l + t[p].r >> 1;
if (mid >= l)
update(p << 1, l, r, k);
if (r >= mid + 1)
update(p << 1 | 1, l, r, k);
up(p);
}
ll getans(ll p, ll l, ll r) {
if (t[p].l >= l && t[p].r <= r)
return t[p].sum;
push_down(p);
ll ans = 0;
ll mid = t[p].l + t[p].r >> 1;
if (l <= mid)
ans += getans(p << 1, l, r);
if (r >= mid + 1)
ans += getans(p << 1 | 1, l, r);
return ans;
}
//================== 以上为线段树模板 ====================
//================== 以下为树剖操作模板 ====================
inline void updatetree(ll s, ll t, ll c) { // s到t的简单路径加上c
while (top[s] != top[t]) { //倍增思想，深度大的往上跳
if (dep[top[s]] > dep[top[t]])
swap(s, t); //默认t深度大
update(1, id[top[t]], id[t], c); //先维护这一段链
t = fa[top[t]]; //跳到这个链头的父节点，维护下一个链
}
if (dep[s] > dep[t])
swap(s, t); //默认t深度大
update(1, id[s], id[t], c); //维护s与现在t(同深度)的链
}
inline ll getanstree(ll s, ll t) { //查询s到t的简单路径权值和
ll ans = 0;
while (top[s] != top[t]) { //倍增思想，深度大的往上跳
if (dep[top[s]] > dep[top[t]])
swap(s, t); //默认t深度大
ans += getans(1, id[top[t]], id[t]); //先查询这一段链
t = fa[top[t]]; //跳到这个链头的父节点，查询下一个链
}
if (dep[s] > dep[t])
swap(s, t); //默认t深度大
ans += getans(1, id[s], id[t]); //查询s与现在t(同深度)的链
return ans;
}
inline void updateson(ll x, ll t) { //以x为根的子树加上t
if (x == r)
update(1, 1, n, t); //当 x=root时，x就是此时整棵树的根，那么就是全局修改。
else {
ll LCA = lca(x, r);
if (LCA != x) //若root不在x的子树中，正常修改
update(1, id[x], id[x] + size[x] - 1, t);
else { //若在子树内，修改它到根的第一个儿子子树的补集
ll u = find(x, r);
update(1, 1, n, t);
update(1, id[u], id[u] + size[u] - 1, -t);
}
}
}
inline ll getansson(ll x) { //以x为根的子树加上t
if (x == r)
return getans(1, 1, n); //当 x=root时，x就是此时整棵树的根，那么就是全局查询。
else {
ll LCA = lca(x, r);
if (LCA != x) //若root不在x的子树中，正常查询
return getans(1, id[x], id[x] + size[x] - 1);
else { //若在子树内，查询它到根的第一个儿子子树的补集
ll u = find(x, r);
return getans(1, 1, n) - getans(1, id[u], id[u] + size[u] - 1);
}
}
}
//================== 以上为树剖操作模板 ====================
//================== 以下为dfs ====================
inline void dfs1(ll x, ll fath, ll deep) { // x当前节点，f父亲，deep深度
dep[x] = deep; //标记每个点的深度
fa[x] = fath; //标记每个点的父亲
size[x] = 1; //标记每个非叶子节点的子树大小
ll maxson = -1; //记录重儿子的儿子数
for (ll i = head[x]; i; i = edge[i].pre) {
ll y = edge[i].to;
if (y == fath)
continue;
dfs1(y, x, deep + 1);
size[x] += size[y]; //把它的儿子数加到它身上
if (size[y] > maxson) { //标记每个非叶子节点的重儿子编号
son[x] = y;
maxson = size[y];
}
}
}
ll tim;
inline void dfs2(ll x, ll fst) { // x当前节点，fst当前链的顶端
id[x] = ++tim; //标记每个点dfs序
w[tim] = a[x]; //赋每个点的初始值
top[x] = fst; //标记这个点所在链的顶端
if (!son[x])
return; //如果没有儿子则返回
dfs2(son[x], fst); //按先处理重儿子
for (ll i = head[x]; i; i = edge[i].pre) {
ll y = edge[i].to;
if (y == fa[x] || y == son[x])
continue;
dfs2(y, y); //轻儿子都有一条从它自己开始的链
}
}
//================== 以上为dfs ====================
inline void add(ll u, ll v) { //链式前向星
edge[++cnt].pre = head[u];
edge[cnt].to = v;
head[u] = cnt;
}
int main() {
n = read();
r = 1;
for (ll i = 1; i <= n; i++) a[i] = read();
for (ll i = 1; i < n; i++) {
ll a;
a = read();
add(a, i + 1), add(i + 1, a);
}
dfs1(r, 0, 1);
dfs2(r, r);
build(1, 1, n);
m = read();
for (ll i = 1; i <= m; i++) {
ll opt = read(), x = read();
if (opt == 1)
r = x;
if (opt == 2) {
ll y = read(), z = read();
updatetree(x, y, z);
}
if (opt == 4) {
ll y = read();
cout << getanstree(x, y) << endl;
}
if (opt == 3) {
ll z = read();
updateson(x, z);
}
if (opt == 5)
cout << getansson(x) << endl;
}
return 0;
}