树链剖分——轻重链剖分

2022年01月27日，第十三天

1. 题目链接：P3384 【模板】轻重链剖分/树链剖分

思路：树链剖分直接搞，时间复杂度为 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n) ，通过模板题，我们可以了解到，树链剖分是用来划分树的路径的一个有效工具，它把任意两点之间的简单路径划分成 $O(logn)$ 段线性区间，当我们得到 $dfs$ 序之后套上线段树时，能够轻松地维护树上的某条链的信息。细节看代码注释。

#include <bits/stdc  .h>
#define ull unsigned long long
#define ll long long
#define re register
#define endl '\n'

using namespace std;

const int MOD = 998244353;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double Pi = acos(-1.0);
const int N = 1e5   5, M = N << 1;

#define ls (x << 1)
#define rs (x << 1 | 1)

int n, m, w[N], rt, P;
int h[N], e[M], ne[M], idx; // 链式前向星
int id[N], nw[N], cnt;				
int dep[N]; // 当前结点的深度
int sz[N];	// 当前结点子树的大小
int top[N];	// 当前结点所在重链的最上的结点编号
int fa[N];	// 当前结点的父亲节点
int son[N]; // 当前结点的重儿子
struct Tree {
    int l, r;
    ll add, sum;
}tr[N << 2]; // 线段树信息
void add_edge (int u, int v) {
    e[idx] = v;
    ne[idx] = h[u];
    h[u] = idx   ;
}

void dfs1 (int u, int p, int depth) {  // 用来处理重儿子
    dep[u] = depth, fa[u] = p, sz[u] = 1;
    for (int i = h[u]; ~ i; i = ne[i]) {
        int j = e[i];
        if (j == p) continue;
        dfs1 (j, u, depth   1);	
        sz[u]  = sz[j];	
        if (sz[son[u]] < sz[j]) son[u] = j; // 所有儿子中子树最大为重儿子
    }
}

void dfs2 (int u, int t) {	// 处理 dfs 序
    id[u] =    cnt, nw[cnt] = w[u], top[u] = t;
    if (! son[u]) return ;
    dfs2 (son[u], t);	// 重儿子的 top 是轻儿子传下来的
    for (int i = h[u]; ~ i; i = ne[i]) {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2 (j, j);	// 轻儿子的 top 是自己
    }
}

void pushup (int x) {
    tr[x].sum = (tr[ls].sum   tr[rs].sum) % P;
}

void pushdown (int x) {
    Tree &p = tr[x], &lson = tr[ls], &rson = tr[rs];
    if (p.add) {
        lson.add = (p.add   lson.add) % P;
        lson.sum = (lson.sum   p.add * (lson.r - lson.l   1) % P) % P;
        rson.add = (p.add   rson.add) % P;
        rson.sum = (rson.sum   p.add * (rson.r - rson.l   1) % P) % P;
        p.add = 0;
    }
}

void build (int l, int r, int x = 1) {
    tr[x] = {l, r, 0, nw[r]};
    if (l == r) return;
    int mid = (l   r) >> 1;
    build (l, mid, ls), build (mid   1, r, rs);
    pushup (x);
}

void update (int l, int r, int v, int x = 1) {
    if (l <= tr[x].l && tr[x].r <= r) {
        tr[x].add = (tr[x].add   v) % P;
        tr[x].sum = (tr[x].sum   (ll)v * (tr[x].r - tr[x].l   1) % P) % P;
        return ;
    }
    pushdown (x);
    int mid = (tr[x].l   tr[x].r) >> 1;
    if (l <= mid) update (l, r, v, ls);
    if (r >  mid) update (l, r, v, rs);
    pushup (x);
}

ll query (int l, int r, int x = 1) {
    if (l <= tr[x].l && tr[x].r <= r) 
        return tr[x].sum;
    pushdown (x);
    int mid = (tr[x].l   tr[x].r) >> 1;
    ll res = 0;
    if (l <= mid) res  = query (l, r, ls);
    if (r >  mid) res  = query (l, r, rs);
    return res % P;
}

void update_path (int x, int y, int v) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap (x, y);
        update (id[top[x]], id[x], v);
        x = fa[top[x]];
    }
    if (dep[x] < dep[y]) swap (x, y);
    update (id[y], id[x], v);
}

ll ask_path (int x, int y) {
    ll res = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap (x, y);
        res = (res   query (id[top[x]], id[x])) % P;
        x = fa[top[x]];
    }
    if (dep[x] < dep[y]) swap (x, y);
    return (res  = query (id[y], id[x])) % P;
}

void update_tree (int x, int v) {
    update (id[x], id[x]   sz[x] - 1, v);
}

ll ask_tree (int x) {
    return query (id[x], id[x]   sz[x] - 1);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m >> rt >> P;
    for (int i = 1; i <= n; i   ) cin >> w[i];
    memset (h, -1, sizeof (h));
    for (int i = 1; i < n; i   ) {
        int u, v; cin >> u >> v;
        add_edge (u, v), add_edge (v, u);
    }
    dfs1 (rt, -1, 1); 	// 处理重儿子
    dfs2 (rt, rt);		// 处理 dfs 序
    build (1, n);
    int op, x, y, z;
    while (m --) {
        cin >> op;
        if (op == 1) {
            cin >> x >> y >> z;
            update_path (x, y, z);
        }
        if (op == 2) {
            cin >> x >> y;
            cout << ask_path (x, y) << endl;
        }
        if (op == 3) {
            cin >> x >> z;
            update_tree (x, z);
        }
        if (op == 4) {
            cin >> x;
            cout << ask_tree (x) << endl;
        }
    }
    return 0;
}

2. 题目链接：P2146 [NOI2015] 软件包管理器

思路：树链剖分裸题，时间复杂度 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n) 。

#include <bits/stdc  .h>
#define ull unsigned long long
#define ll long long
#define re register
#define endl '\n'

using namespace std;

const int MOD = 998244353;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double Pi = acos(-1.0);
const int N = 1e5   5;

int h[N], e[N], ne[N], idx;
int dep[N], sz[N], top[N], fa[N], son[N];
int id[N], cnt, n, qur;
struct node {
    int l, r, lazy, sum;
}t[N << 2];

void add_edge (int u, int v) {
    e[idx] = v;
    ne[idx] = h[u];
    h[u] = idx   ;
}

void dfs1 (int u, int depth) {
    dep[u] = depth, sz[u] = 1;
    for (int i = h[u]; ~ i; i = ne[i]) {
        int v = e[i];
        dfs1 (v, depth   1);
        sz[u]  = sz[v];
        if (sz[son[u]] < sz[v]) son[u] = v;
    }
}

void dfs2 (int u, int T) {
    id[u] =    cnt, top[u] = T;
    if (! son[u]) return ;
    dfs2 (son[u], T);
    for (int i = h[u]; ~ i; i = ne[i]) {
        int v = e[i];
        if (v == son[u]) continue;
        dfs2 (v, v);
    }
}

#define ls (x << 1) 
#define rs (x << 1 | 1)

void build (int l, int r, int x = 1) {
    t[x] = {l, r, -1, 0};
    if (l == r) return ;
    int mid = (l   r) >> 1;
    build (l, mid, ls), build (mid   1, r, rs);
}

void pushdown (int x) {
    node &p = t[x], &lson = t[ls], &rson = t[rs];
    if (p.lazy != -1) {
        lson.lazy = rson.lazy = p.lazy;
        lson.sum = p.lazy * (lson.r - lson.l   1);
        rson.sum = p.lazy * (rson.r - rson.l   1);
        p.lazy = -1;
    }
}

void pushup (int x) {
    t[x].sum = t[ls].sum   t[rs].sum;
}

void update (int l, int r, int v, int x = 1) {  
    if (l <= t[x].l && t[x].r <= r) {
        t[x].lazy = v;
        t[x].sum = v * (t[x].r - t[x].l   1);
        return ;
    }
    pushdown (x);
    int mid = (t[x].l   t[x].r) >> 1;
    if (l <= mid) update (l, r, v, ls);
    if (r >  mid) update (l, r, v, rs);
    pushup (x);
}

int query (int l, int r, int x = 1) {
    if (l <= t[x].l && t[x].r <= r) 
        return t[x].sum;
    pushdown (x);
    int mid = (t[x].l   t[x].r) >> 1, res = 0;
    if (l <= mid) res  = query (l, r, ls);
    if (r >  mid) res  = query (l, r, rs);
    return res;
}

void update_path (int v, int x, int y = 1) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap (x, y);
        update (id[top[x]], id[x], v);
        x = fa[top[x]];
    }
    if (dep[x] < dep[y]) swap (x, y);
    update (id[y], id[x], v);
}

void update_tree (int x, int v) {
    update (id[x], id[x]   sz[x] - 1, v);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n, fa[1] = 1;
    memset (h, -1, sizeof (h));
    for (int i = 2; i <= n; i   ) {
        int p; cin >> p, p   ;
        add_edge (p, i), fa[i] = p;
    }
    dfs1 (1, 1), dfs2 (1, 1);
    build (1, n);
    cin >> qur;
    while (qur --) {
        int x; 
        char op[20]; 
        cin >> op >> x, x   ;
        if (* op == 'i') {
            int now = t[1].sum;
            update_path (1, x);
            cout << t[1].sum - now << endl;
        }else {
            int now = t[1].sum;
            update_tree (x, 0);
            cout << now - t[1].sum << endl;
        }
    }
    return 0;
}

这篇好文章是转载于：学新通技术网