洛谷 P3384 树链剖分模板+代码解释

题意：一棵n个结点的树，每个点有点权，有如下操作：

1 x y c：给x到y的链上所有结点点权加上c

2 x y：查询x到y链上的点权和

3 x c：给x及其子树上的所有结点点权加上c

4 x：查询x及其子树所有结点的点权和

第一遍dfs：预处理，子树大小，节点深度，顺便标记结点的父亲结点编号

void dfs(int u, int fa, int cnt){
    sum[u] = 1; //sum[u]表示u的子树大小，首先只有自己
    rk[u] = cnt; //深度为cnt
    f[u] = fa; //标记父节点
    for (int i = head[u]; i; i = e[i].nxt){
        int v = e[i].v;
        if (v == fa) continue;
        dfs(v, u, cnt+1);
        sum[u] += sum[v]; //加上儿子v的子树大小
        if (sum[v] > sum[son[u]]) son[u] = v; //如果v的子树比当前重儿子大，更新v为重儿子
    }
}

第二遍dfs：处理每个点的顶端，按dfs序给每个点分配一个编号，使其能够映射到线段树上

void dfs2(int u, int t){
    top[u] = t;//top是能沿重链走到的最上方的点
    idx[u] = ++cnt; //打上时间戳
    a[cnt] = b[u]; //映射到线段树的区间上
    if (!son[u]) return; //这是叶节点
    dfs2(son[u], t); //沿重链走
    for (int i = head[u]; i; i = e[i].nxt){
        int v = e[i].v;
        if (!idx[v]) dfs2(v, v); //处理轻儿子
    }
}

怎样利用树链剖分的轻重链（主要是重链）加速链上的修改？

类似LCA的思想，x，y较深的一个往上走

1. 将深的那个结点往上提，直至x，y在同一条重链，每次都对走过的链上结点修改。

2. 修改x，y之间的链，这条链是重链

这部分代码：

void TreeAdd(int x, int y, LL c){
    while (top[x] != top[y]){ //不在同一重链
        if (rk[top[x]] < rk[top[y]]) swap(x, y);
        upd(idx[top[x]], idx[x], 1, c);
        x = f[top[x]]; //走到顶端的父亲
    }
    if (rk[x] > rk[y]) swap(x, y);
    upd(idx[x], idx[y], 1, c); //修改现在所在的这一条重链
}

然后就只是普通的线段树操作而已了

完整代码：

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<iostream>
  5 #define LL long long
  6 #define debug(x) cout << "[" << x << "]" << endl
  7 #define lid id << 1
  8 #define rid id << 1 | 1
  9 using namespace std;
 10 
 11 const int mx = 1e5+10;
 12 
 13 struct tree{
 14     int l, r;
 15     LL sum, lazy;
 16 }tree[mx<<2];
 17 
 18 struct edge{
 19     int v, nxt;
 20 }e[mx<<1];
 21 int tot = 1, mod;
 22 int head[mx], sum[mx], rk[mx], son[mx], f[mx], top[mx], idx[mx];
 23 LL a[mx], b[mx];
 24 
 25 void add(int u, int v){
 26     e[tot].v = v;
 27     e[tot].nxt = head[u];
 28     head[u] = tot++;
 29 }
 30 
 31 void dfs(int u, int fa, int cnt){
 32     sum[u] = 1;
 33     rk[u] = cnt;
 34     f[u] = fa;
 35     for (int i = head[u]; i; i = e[i].nxt){
 36         int v = e[i].v;
 37         if (v == fa) continue;
 38         dfs(v, u, cnt+1);
 39         sum[u] += sum[v];
 40         if (sum[v] > sum[son[u]]) son[u] = v;
 41     }
 42 }
 43 
 44 int cnt = 0;
 45 void dfs2(int u, int t){
 46     top[u] = t;
 47     idx[u] = ++cnt;
 48     a[cnt] = b[u];
 49     if (!son[u]) return;
 50     dfs2(son[u], t);
 51     for (int i = head[u]; i; i = e[i].nxt){
 52         int v = e[i].v;
 53         if (!idx[v]) dfs2(v, v);
 54     }
 55 }
 56 
 57 void push_up(int id){
 58     tree[id].sum = (tree[lid].sum + tree[rid].sum)%mod;
 59 }
 60 
 61 void build(int l, int r, int id){
 62     tree[id].l = l;
 63     tree[id].r = r;
 64     tree[id].lazy = 0;
 65     if (l == r) {
 66         tree[id].sum = a[l]%mod;
 67         return;
 68     }
 69     int mid = (l+r)>>1;
 70     build(l, mid, lid);
 71     build(mid+1, r, rid);
 72     push_up(id);
 73 }
 74 
 75 void push_down(int id){
 76     if (tree[id].lazy != 0){
 77         LL x = tree[id].lazy;
 78         tree[lid].lazy += x;
 79         tree[lid].lazy %= mod;
 80         tree[rid].lazy += x;
 81         tree[rid].lazy %= mod;
 82         tree[lid].sum += x*(tree[lid].r-tree[lid].l+1);
 83         tree[lid].sum %= mod;
 84         tree[rid].sum += x*(tree[rid].r-tree[rid].l+1);
 85         tree[rid].sum %= mod;
 86         tree[id].lazy = 0;
 87     }
 88 }
 89 
 90 void upd(int l, int r, int id, LL c){
 91     if (tree[id].l == l && tree[id].r == r){
 92         tree[id].sum += c*(r-l+1);
 93         tree[id].sum %= mod;
 94         tree[id].lazy += c;
 95         tree[id].lazy %= mod;
 96         return;
 97     }
 98     push_down(id);
 99     int mid = (tree[id].l + tree[id].r)>>1;
100     if (r <= mid) upd(l, r, lid, c);
101     else if (mid < l) upd(l, r, rid, c);
102     else {
103         upd(l, mid, lid, c);
104         upd(mid+1, r, rid, c);
105     }
106     push_up(id);
107 }
108 
109 LL query(int l, int r, int id){
110     if (tree[id].l == l && tree[id].r == r) return tree[id].sum%mod;
111     push_down(id);
112     int mid = (tree[id].l + tree[id].r)>>1;
113     if (r <= mid) return query(l, r, lid)%mod;
114     else if (mid < l) return query(l, r, rid)%mod;
115     return (query(l, mid, lid) + query(mid+1, r, rid))%mod;
116 }
117 
118 void TreeAdd(int x, int y, LL c){
119     while (top[x] != top[y]){
120         if (rk[top[x]] < rk[top[y]]) swap(x, y);
121         upd(idx[top[x]], idx[x], 1, c);
122         x = f[top[x]];
123     }
124     if (rk[x] > rk[y]) swap(x, y);
125     upd(idx[x], idx[y], 1, c);
126 }
127 
128 LL TreeSum(int x, int y){
129     LL ans = 0;
130     while (top[x] != top[y]){
131         if (rk[top[x]] < rk[top[y]]) swap(x, y);
132         ans += query(idx[top[x]], idx[x], 1);
133         ans %= mod;
134         x = f[top[x]];
135     }
136     if (rk[x] > rk[y]) swap(x, y);
137     ans += query(idx[x], idx[y], 1);
138     ans %= mod;
139     return ans;
140 }
141 
142 int main(){
143     int n, m, r, u, v;
144     scanf("%d%d%d%d", &n, &m, &r, &mod);
145     for (int i = 1; i <= n; i++) scanf("%lld", &b[i]);
146     for (int i = 2; i <= n; i++){
147         scanf("%d%d", &u, &v);
148         add(u, v);
149         add(v, u);
150     }
151     dfs(r, 0, 1);
152     dfs2(r, r);
153     build(1, n, 1);
154     int op, x, y;
155     LL c;
156     while (m--){
157         scanf("%d%d", &op, &x);
158         if (op == 1) {
159             scanf("%d%lld", &y, &c);
160             TreeAdd(x, y, c);
161         }
162         else if (op == 2){
163             scanf("%d", &y);
164             printf("%lld
", TreeSum(x, y));
165         }
166         else if (op == 3){
167             scanf("%lld", &c);
168             upd(idx[x], idx[x]+sum[x]-1, 1, c%mod);
169         }
170         else printf("%lld
", query(idx[x], idx[x]+sum[x]-1, 1));
171     }
172     return 0;
173 }

View Code