dfs序基础1
给一棵有根树，这棵树由编号为 \(1\dots N\) 的 \(N\) 个结点组成。根结点的编号为 \(R\)。每个结点都有一个权值，结点 \(i\) 的权值为 \(v_i\)。
接下来有 \(M\) 组操作，操作分为两类：
1 a x，表示将结点 \(a\) 的权值增加 \(x\)；2 a，表示求结点 \(a\) 的子树上所有结点的权值之和。
输入 #1
10 14 9
12 -6 -4 -3 12 8 9 6 6 2
8 2
2 10
8 6
2 7
7 1
6 3
10 9
2 4
10 5
1 4 -1
2 2
1 7 -1
2 10
1 10 5
2 1
1 7 -5
2 5
1 1 8
2 7
1 8 8
2 2
1 5 5
2 6
输出 #1
21
34
12
12
23
31
4
$ 1\leqslant N, M\leqslant 10^6, 1\leqslant R\leqslant N, -10^6\leqslant v_i, x\leqslant 10^6. $
思路
\(dfs\)序，访问每一个节点，每到一个节点记录一次时间，同时时间\(++\)
即 \(u\) 的进入时间为 \(s[u]\) ，全部访问完子节点退出时的时间为 \(e[u]\)
重新编号 \(u\) 为 \(s[u]\) ， 那么发现对于
任一点 \(u\)，它子树内的任一点 \(v\)，\(s[u] <= v <= e[u]\) 即点 \(v\) 访问的时间被 \(u\) 的两个时间完全包含（u，v为重新编号为重新编号的），这时因为在访问完 \(u\) 内的所有点前不会退出到其它点
如图
上图中红色数字就是对应节点的 s, 蓝色数字就是对应节点的 e
把重编号后的节点进行操作，发现修改就是将节点对应下标的位置操作，而查询一个子树内的信息，就是查询一个区间内的信息
于是用树状数组维护就可以了
#include<bits/stdc++.h>
#define int long long
#define fore(i, a, b) for( int i = (a); i <= (b); ++ i)
#define repe(i, a, b) for( int i = (a); i >= (b); -- i)
using namespace std;
const int N = 1e6 + 10;
int n, m, r;
int dfn;
int s[N], e[N];
int t[N], a[N];
vector<int>G[N];
inline int lowbit(int x)
{return x & (-x);
}
void update(int u,int v)
{while(u <= n){t[u] += v;u += lowbit(u);}
}
int sum(int u)
{int res = 0;while(u > 0){res += t[u];u -= lowbit(u);}return res;
}
void dfs(int u,int fa)
{s[u] = ++ dfn;update(dfn, a[u]);fore(i, 0, G[u].size() - 1){int v = G[u][i];if(v == fa)continue;dfs(v, u);}e[u] = dfn;
}
signed main()
{ios::sync_with_stdio(false);cin >> n >> m >> r;fore(i, 1, n) cin >> a[i];fore(i, 1, n - 1){int u, v;cin >> u >> v;G[u].push_back(v);G[v].push_back(u);}dfs(r, 0);while(m --){int orr, u, v;cin >> orr >> u;if(orr == 1){cin >> v;update(s[u], v);}else{cout << sum(e[u]) - sum(s[u] - 1) << '\n';}}return 0;
}dfs序基础2
给一棵有根树，这棵树由编号为 \(1\dots N\) 的 \(N\) 个结点组成。根结点的编号为 \(R\)。
每个结点都有一个权值，结点 \(i\) 的权值为 \(v_i\)。
接下来有 \(M\) 组操作，操作分为两类：
1 a x，表示将结点 \(a\) 的子树上所有结点的权值增加 \(x\)；2 a，表示求结点 \(a\) 的子树上所有结点的权值之和。
输入 #1
10 14 9
12 -6 -4 -3 12 8 9 6 6 2
8 2
2 10
8 6
2 7
7 1
6 3
10 9
2 4
10 5
1 4 -1
2 2
1 7 -1
2 10
1 10 5
2 1
1 7 -5
2 5
1 1 8
2 7
1 8 8
2 2
1 5 5
2 6
输出 #1
21
33
16
17
27
76
30
\(1\leqslant N, M\leqslant 10^6, 1\leqslant R\leqslant N, -10^6\leqslant v_i, x\leqslant 10^6.\)
思路
这题和上题几乎一样，注意唯一区别在于本题的修改操作是对节点及其子树一起操作，所以是一个区间修改，区间查询的问题
使用线段树维护每一个点的权值即可
#include<bits/stdc++.h>
#define int long long
#define fore(i, a, b) for( int i = (a); i <= (b); ++ i)
#define repe(i, a, b) for( int i = (a); i >= (b); -- i)
using namespace std;
const int N = 1e6 + 10;
int n, m, Root , M;
int dfn;
int s[N], e[N];
int t[N], a[N];
int num[N];
int sum[N << 2], lazy[N << 2];
vector<int>G[N];
inline int ls(int p){return p << 1;}
inline int rs(int p){return ((p << 1) | 1);}
inline void pushup(int p){sum[p] = sum[ls(p)] + sum[rs(p)];}
void uy(int p,int l,int r,int k)
{sum[p] += (r - l + 1) * k;lazy[p] += k;
}
void pushdown(int p,int l,int r)
{int mid = (l + r) >> 1;if(lazy[p] && l != r){sum[ls(p)] += lazy[p] * (mid - l + 1);sum[rs(p)] += lazy[p] * (r - mid);lazy[ls(p)] += lazy[p];lazy[rs(p)] += lazy[p];lazy[p] = 0;}
}
void build(int p,int l,int r)
{if(l == r){sum[p] = a[num[l]];return;}int mid = (l + r) >> 1;build(ls(p), l, mid);build(rs(p), mid + 1, r);pushup(p);return;
}
void update(int p,int l,int r,int L,int R,int k)
{if(L <= l && r <= R){uy(p, l, r, k);return;}int mid = (l + r) >> 1;pushdown(p, l, r);if(L <= mid) update(ls(p), l, mid, L, R, k);if(R >= mid + 1) update(rs(p), mid + 1, r, L, R, k);pushup(p);}int query(int p,int l,int r,int L,int R)
{if(L <= l && r <= R){return sum[p];}int mid = (l + r) >> 1;pushdown(p, l, r);int res = 0;if(L <= mid) res += query(ls(p), l, mid, L, R);if(R >= mid + 1) res += query(rs(p), mid + 1, r, L, R);return res;
}void dfs(int u,int fa)
{s[u] = ++ dfn;num[dfn] = u;fore(i, 0, G[u].size() - 1){int v = G[u][i];if(v == fa)continue;dfs(v, u);}e[u] = dfn;return;
}signed main()
{ios::sync_with_stdio(false);cin >> n >> m >> Root;fore(i, 1, n) cin >> a[i];fore(i, 1, n - 1){int u, v;cin >> u >> v;G[u].push_back(v);G[v].push_back(u);}dfs(Root, 0);build(1, 1, n);while(m --){int orr, u, v;cin >> orr >> u;if(orr == 1){cin >> v;update(1, 1, n, s[u], e[u], v);}else{cout << query(1, 1, n, s[u], e[u]) << '\n';}}return 0;
}P2982
题意简化就是每一次将一个点的权值加一，同时查询根节点到当前节点的权值和
发现当 \(u\) 的权值加 \(1\) 是作影响到的一定是他的子节点， 因为子树外的节点和根节点的路径不会经过它，所一用上一题的方法，每一次把一个点和他的所有子节点 \(+1\)
查询即可
#include<bits/stdc++.h>
#define int long long
#define fore(i, a, b) for( int i = (a); i <= (b); ++ i)
#define repe(i, a, b) for( int i = (a); i >= (b); -- i)
using namespace std;
const int N = 1e6 + 10;
int n, m, r;
int dfn;
int s[N], e[N], num[N];
int t[N];
vector<int>G[N];
inline int lowbit(int x)
{return x & (-x);
}
void update(int u,int v)
{while(u <= n){t[u] += v;u += lowbit(u);}
}
int sum(int u)
{int res = 0;while(u > 0){res += t[u];u -= lowbit(u);}return res;
}
void dfs(int u,int fa)
{s[u] = ++ dfn;num[dfn] = u;fore(i, 0, G[u].size() - 1){int v = G[u][i];if(v == fa)continue;dfs(v, u);}e[u] = dfn;
}
signed main()
{ios::sync_with_stdio(false);cin >> n;fore(i, 1, n - 1){int u, v;cin >> u >> v;G[u].push_back(v);G[v].push_back(u);}dfs(1, 0);fore(i, 1, n){int u;cin >> u;cout << sum(s[u]) << '\n';update(s[u], 1);update(e[u] + 1, -1);}return 0;
}P3128
树上差分
题意是说每一次将一条路径上的所有点权值 \(+1\) 最后查询权值最大点的权值
想序列上的差分是怎样的？
对 \(l, r\) 差分时将 \(l\) 的点 \(+ val\) ，\(r\) 的点 $ - val$，最后求前缀和，就实现了对 \(l, r\) 进行 \(+ val\) 的操作，因为在前缀和时，在 \(l\) 加上的值会影响后面左右的点，但是为了避免他影响到\(r\)后面的点，就在\(r + 1\) 减去这个值
同样将差分运用的树上
对 \(u\) 到 \(v\) 的路径操作，直接在 \(u\) 和 \(v\) 加上一个值，在做一个类似求子树大小的东西，这样加上的值会一路往上传
但是在\(lca(u, v)\) -> \(p\) 是会多传一个，所以在 \(p\) 减一个，在p的父亲再减一个，防止影响上面的点
#include<bits/stdc++.h>
#define int long long
#define fore(i, a, b) for( int i = (a); i <= (b); ++ i)
#define repe(i, a, b) for( int i = (a); i >= (b); -- i)
using namespace std;
const int N = 1e5 + 10;
int n, k, ans = -1e9;
vector<int>G[N];
int dis[N], f[N][20];
int c[N];
void dfs(int u,int fa)
{dis[u] = dis[fa] + 1;f[u][0] = fa;fore(i, 1, 19)f[u][i] = f[f[u][i - 1]][i - 1];fore(i, 0, G[u].size() - 1){int v = G[u][i];if(v == fa)continue;dfs(v, u);}
}
int lca(int x,int y)
{if(dis[x] < dis[y]) swap(x, y);repe(i, 19, 0){if(dis[f[x][i]] >= dis[y]) x = f[x][i];}if(x == y)return x;repe(i, 19, 0){if(f[x][i] != f[y][i]){x = f[x][i];y = f[y][i];}}return f[x][0];
}
void dfss(int u,int fa)
{fore(i, 0, G[u].size() - 1){int v = G[u][i];if(v == fa)continue;dfss(v, u);c[u] += c[v];}ans = max(ans, c[u]);
}
signed main()
{ios::sync_with_stdio(false);cin >> n >> k;fore(i, 1, n - 1){int u, v;cin >> u >> v;G[u].push_back(v);G[v].push_back(u);}dfs(1, 0);fore(i, 1, k){int u, v, p;cin >> u >> v;p = lca(u, v);c[u] ++;c[v] ++;c[p] --;c[f[p][0]] --;}dfss(1, 0);cout << ans << '\n';return 0;
}
