前置芝士：
时间戳
在树的优先深度遍历中，以每个节点第一次被访问的顺序，依次给予这 \(N\) 个节点 \(1~n\) 的整数标记该标记被称为时间戳。通常用 \(dfn[x]\) 表示 \(x\) 节点上的时间戳。
树的 DFS 序
定义：
在树的深度优先遍历中，对于每个节点进入递归后以及即将回溯前各记录一次该点的编号，最后产生长度为 \(2~n\) 的序列就被称为树的 \(DFS\) 序。
特点：
-
每次节点在序列中恰好出现两次。
-
设 \(L[x]\) , \(R[x]\) 分别表示 $$x 出现的两次的位置。那么区间 \([L[x] \sim R[x]]\) 对应的就是树上的以 \(x\) 为根的子树.
例题1：LOJ 144. DFS 序 1
题目描述
- 树上 \(u\) 节点权值 \(+x\)。
- 询问 \(u\) 子树的权值和。
题目分析
求出dfs序
对于操作1:在序列上进行单点加
对于操作2:在序列上区间求和
直接树状数组维护。
code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
struct edge{
int v, last;
}E[N * 2];
int L[N], R[N], n, m, root, q, t1, u, v, head[N], tot, k;
LL c[N], val[N], t2;
void ins(int u, int v){
E[++tot].v = v;
E[tot].last = head[u];
head[u] = tot;
}
void dfs(int x, int fa){
L[x] = ++k;
for(int i = head[x]; i; i = E[i].last){
int v = E[i].v;
if(v == fa) continue;
dfs(v, x);
}
R[x] = k;
}
int lowbit(int x){
return x & -x;
}
void add(int x, LL y){
for(; x <= k; x += lowbit(x)) c[x] += y;
}
LL ask(int x){
LL res = 0;
for(; x; x -= lowbit(x)) res += c[x];
return res;
}
int main(){
scanf("%d%d%d", &n, &m, &root);
for(int i = 1; i <= n; i++){
scanf("%lld", &val[i]);
}
for(int i = 1; i < n; i++){
scanf("%d%d", &u, &v);
ins(u, v);
ins(v, u);
}
dfs(root, 0);
for(int i = 1; i <= n; i++) add(L[i], val[i]);
while(m--){
scanf("%d", &q);
if(q == 1){
scanf("%d%lld", &t1, &t2);
add(L[t1], t2);
}
else{
scanf("%d", &t1);
printf("%lld\n", ask(R[t1]) - ask(L[t1] - 1));
}
}
return 0;
}
例题2： LOJ 145. DFS 序 2
题目描述
- 树上子树修改。
- 查询以 \(u\) 为根的子树权值和。
题目分析
求出 \(DFS\) 序，相当于在 \(DFS\) 序上进行 区间加 和 区间求和。
树状数组 或者 带懒标记的线段树。
code
#include<bits/stdc++.h>//区间修改，区间查询（树状数组）
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
struct edge{
int v, last;
}E[N * 2];
int L[N], R[N], n, m, root, q, t1, u, v, head[N], tot, k;
LL c[2][N], val[N], t2, sum[N];//c[0][i] 维护 b[i], c[1][i] 维护 i * b[i]
void ins(int u, int v){
E[++tot].v = v;
E[tot].last = head[u];
head[u] = tot;
}
void dfs(int x, int fa){
L[x] = ++k;
sum[k] = sum[k - 1] + val[x];//先处理好前缀和
for(int i = head[x]; i; i = E[i].last){
int v = E[i].v;
if(v == fa) continue;
dfs(v, x);
}
R[x] = k;
}
int lowbit(int x){
return x & -x;
}
void add(int t, int x, LL y){
for(; x <= k; x += lowbit(x)) c[t][x] += y;
}
LL ask(int t, int x){
LL res = 0;
for(; x; x -= lowbit(x)) res += c[t][x];
return res;
}
int main(){
scanf("%d%d%d", &n, &m, &root);
for(int i = 1; i <= n; i++){
scanf("%lld", &val[i]);
}
for(int i = 1; i < n; i++){
scanf("%d%d", &u, &v);
ins(u, v);
ins(v, u);
}
dfs(root, 0);
while(m--){
scanf("%d", &q);
if(q == 1){
scanf("%d%lld", &t1, &t2);
add(0, L[t1], t2);
add(0, R[t1] + 1, -t2);
add(1, L[t1], L[t1] * t2);
add(1, R[t1] + 1, -(R[t1] + 1) * t2);
}
else{
scanf("%d", &t1);
int r = R[t1], l = L[t1];
printf("%lld\n", sum[r] - sum[l - 1] + (r + 1) * ask(0, r) - ask(1,
r) - l * ask(0, l - 1) + ask(1, l - 1));
}
}
return 0;
}
例题3：146. DFS 序 3，树上差分 1
题目描述
- 树上路径中所有节点权值加
- 单节点求值
- 子树权值和查询
题目分析
对于操作 1 可以直接树上差分，随着操作 2 就变成了子树查询。
How 操作3？
设查分后，\(v\) 节点的差分值为 \(val[v]\)。若 \(v\) 再以 \(u\) 为根的子树中，考虑 \(v\) 对于 \(u\) 这个子树权值和的增加量贡献。
\[val[v] \times (dep_v - dep_u + 1) = val[v] * (dep_v-1) \times val[v] \]于是 \(u\) 的子树增加量之和：
\[(\sum_{v \in Tree(u)} val[v] \times dep_v)-(dep_u - 1) \times \sum_{v \in Tree(u)}{val[v]} \]维护2个树状数组即可
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000005, M = 2000005;
int head[N], nxt[M], v[M], edgenum, dep[N], n, m, in[N], out[N], tim, rt, lg[N] = {-1}, st[N][25];
ll f[N], ff[N], a[N];
int lca(int x, int y);
inline void update(ll c[], int x, ll v) {
if (!x)
return;
for (int i = x; i <= n; i += i & -i)
c[i] += v;
}
inline void update(int x, int y, ll v) { // 路径修改所对应的差分修改
update(f, in[x], v);
update(ff, in[x], v * dep[x]);
update(f, in[y], v);
update(ff, in[y], v * dep[y]);
int LCA = lca(x, y), father = st[LCA][0];
update(f, in[LCA], -v);
update(ff, in[LCA], -v * dep[LCA]);
update(f, in[father], -v);
update(ff, in[father], -v * dep[father]);
}
inline ll query(ll c[], int x) {
ll res = 0;
for (int i = x; i; i &= i - 1)
res += c[i];
return res;
}
inline ll query_point(int x) {
return query(f, out[x]) - query(f, in[x] - 1);
}
inline ll query_tree(int x) {
return query(ff, out[x]) - query(ff, in[x] - 1) - query_point(x) * (dep[x] -
1);
}
void add(int x, int y) {
v[++edgenum] = y; //边的数量+1，这条边指向点y
nxt[edgenum] = head[x]; //江这条边的下一条边指向为x的第一条边
head[x] = edgenum; //将x的第一条边重定向为该边
}
void dfs(int x, int father) { //构造st表
in[x] = ++tim;
st[x][0] = father;
dep[x] = dep[father] + 1;
for (int i = 1; i <= lg[dep[x]]; ++i)
st[x][i] = st[st[x][i - 1]][i - 1];
for (int e = head[x]; e; e = nxt[e]) {
if (v[e] != father)
dfs(v[e], x);
}
out[x] = tim;
}//O(nlogn)
int lca(int x, int y) { //找x和y的最近公共祖先
if (dep[x] < dep[y])
swap(x, y); //预设x更深
while (dep[x] > dep[y])
x = st[x][lg[dep[x] - dep[y]]];
if (x == y)
return y;//如果y本是x的祖先,lca即y
for (int i = lg[dep[x]]; i >= 0; i--) {
if (st[x][i] != st[y][i]) {
x = st[x][i];
y = st[y][i];
}
}
return st[x][0];
}//O(logn)
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> rt;
ll op, x, y, v;
for (int i = 1; i <= n; i++) {
cin >> a[i];
lg[i] = lg[i >> 1] + 1;
}
for (int i = 1; i < n; i++) {
cin >> x >> y;
add(x, y);
add(y, x);
}
dfs(rt, 0);
for (int i = 1; i <= n; ++i)
update(i, i, a[i]); // 单个点的初始值 也 看成路径修改
for (; m--;) {
cin >> op >> x;
if (op == 1) {
cin >> y >> v;
update(x, y, v);
} else if (op == 2) {
cout << query_point(x) << "\n";
} else
cout << query_tree(x) << "\n";
}
return 0;
}