重链剖分

重链剖分是一种以 \(O(\log^2 n)\) 时间复杂度维护树上路径，同时支持 dfs 序相关操作的算法。

基本定义

• 子树大小 sz[u]：以 \(u\) 为根的子树中所含节点的数量；
• 重儿子 son[u]：节点 \(u\) 的所有儿子 \(v\) 中，sz[v]最大的一个；
• 重边：由一个非叶子节点指向其重儿子的边；
• 重链：由若干重边组成的连续的链；

算法原理

如果我们设定 dfs 的遍历顺序，使对于任意一个非叶子节点 \(u\)，它的重儿子 son[u] 总是在所有儿子中最先被访问到。这样，一条重链上所有节点的 dfs 序一定是连续的。

我们可以使用线段树维护重链，并将待查询路径分解为若干条重链组成，在分解得到的每一条重链上进行区修区查，再合并所有结果，就能实现路径修改、路径查询。

时间复杂度分析

我们发现，从一个节点 \(u\) 转移到它的一个轻儿子 \(v\) 上， sz[v] 至少减小为 sz[u] 的 \(\frac{1}{2}\)。

因此任意一条自上而下的路径中所包含的重链条数一定不超 \(\log n\) 条（因为连接两条相邻重链的边一定是轻边）。

对每一条重链，线段树的区修区查复杂度的上界是 \(O(\log n)\)。因此单次修改的总时间复杂度上界为 \(O(\log^2 n)\)。

P3384 【模板】重链剖分/树链剖分

该题目中还用一个操作：子树修改子树查询。

我们注意到，树剖的本质仍然是一种 dfs 序，只不过进行了一些合法的调整。因此，子树内所有节点的 dfs 序仍然连续，因此也可以使用普通的 dfs 序线段树维护。

代码

#include<iostream>
#define int long long
using namespace std;
const int N = 1E5 + 10;

struct Edge {
    int v;
    int next;
} pool[2 * N];
int nn, head[N];

void addEdge(int u, int v) {
    pool[++nn] = {v, head[u]};
    head[u] = nn;
}

int n, m, rt, MOD;
int a[N];
int fa[N], sz[N], son[N], top[N], dep[N];

// 维护 sz[u], son[u]
void dfs1(int u, int f) {
    fa[u] = f;
    sz[u] = 1;
    dep[u] = dep[f] + 1;
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v;
        if(v == f) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if(son[u] == 0 || sz[v] > sz[son[u]]) {
            son[u] = v;
        }
    }
}

int dfn[N], id[N], dt;

// 记录 dfs 序
void dfs2(int u, int f, int tp) {
    dfn[u] = ++dt;
    id[dt] = u;
    top[u] = tp;
    if(son[u]) dfs2(son[u], u, tp);
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v;
        if(v == f) continue;
        if(v == son[u]) continue;
        dfs2(v, u, v);
    }
}

namespace seg_tree {

    int sum[4 * N], tag[4 * N];

    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }

    void push_up(int p) {
        sum[p] = (sum[lc(p)] + sum[rc(p)]) % MOD;
    }

    void move_tag(int p, int l, int r, int tg) {
        sum[p] = (sum[p] + tg * (r - l + 1)) % MOD;
        tag[p] = (tag[p] + tg) % MOD;
    }

    void push_down(int p, int l, int r) {
        int mid = (l + r) >> 1;
        move_tag(lc(p), l, mid, tag[p]);
        move_tag(rc(p), mid + 1, r, tag[p]);
        tag[p] = 0;
    }

    void build_tree(int p, int l, int r) {
        if(l == r) {
            move_tag(p, l, r, a[id[l]]);
            return;
        }
        int mid = (l + r) >> 1;
        build_tree(lc(p), l, mid);
        build_tree(rc(p), mid + 1, r);
        push_up(p);
    }

    void modify(int p, int l, int r, int ql, int qr, int val) {
        if(ql <= l && r <= qr) {
            move_tag(p, l, r, val);
            return;
        }
        int mid = (l + r) >> 1;
        push_down(p, l, r);
        if(mid >= ql) modify(lc(p), l, mid, ql, qr, val);
        if(mid < qr) modify(rc(p), mid + 1, r, ql, qr, val);
        push_up(p);
    }

    int query(int p, int l, int r, int ql, int qr) {
        if(ql <= l && r <= qr) {
            return sum[p];
        }
        int mid = (l + r) >> 1, res = 0;
        push_down(p, l, r);
        if(mid >= ql) res += query(lc(p), l, mid, ql, qr);
        if(mid < qr) res += query(rc(p), mid + 1, r, ql, qr);
        return res % MOD;
    }

}

void modify_path(int x, int y, int v) {
    while(true) {
        if(top[x] == top[y]) {
            seg_tree::modify(1, 1, n, min(dfn[x], dfn[y]), max(dfn[x], dfn[y]), v);
            break;
        }
        if(dep[top[x]] > dep[top[y]]) {
            seg_tree::modify(1, 1, n, dfn[top[x]], dfn[x], v);
            x = fa[top[x]];
        } else {
            seg_tree::modify(1, 1, n, dfn[top[y]], dfn[y], v);
            y = fa[top[y]];
        }
    }
}

int query_path(int x, int y) {
    int res = 0;
    while(true) {
        if(top[x] == top[y]) {
            res += seg_tree::query(1, 1, n, min(dfn[x], dfn[y]), max(dfn[x], dfn[y]));
            res %= MOD;
            break;
        }
        if(dep[top[x]] > dep[top[y]]) {
            res += seg_tree::query(1, 1, n, dfn[top[x]], dfn[x]);
            res %= MOD;
            x = fa[top[x]];
        } else {
            res += seg_tree::query(1, 1, n, dfn[top[y]], dfn[y]);
            res %= MOD;
            y = fa[top[y]];
        }
    }
    return res;
}

void modify_tree(int x, int v) {
    seg_tree::modify(1, 1, n, dfn[x], dfn[x] + sz[x] - 1, v);
}

int query_tree(int x) {
    return seg_tree::query(1, 1, n, dfn[x], dfn[x] + sz[x] - 1);
}

signed main() {

    cin >> n >> m >> rt >> MOD;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for(int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }

    dfs1(rt, 0);
    dfs2(rt, 0, rt);

seg_tree::build_tree(1, 1, n);

    while(m--) {
        int op;
        cin >> op;
        if(op == 1) {
            int x, y, v;
            cin >> x >> y >> v;
            modify_path(x, y, v);
        } else if(op == 2) {
            int x, y;
            cin >> x >> y;
            cout << query_path(x, y) << endl;
        } else if(op == 3) {
            int x, v;
            cin >> x >> v;
            modify_tree(x, v);
        } else {
            int x;
            cin >> x;
            cout << query_tree(x) << endl;
        }
    }

    return 0;
}

250610 模拟赛 T2

请点击标题链接查看。

P4211 [LNOI2014] LCA

题意

给定一棵包含 \(n\) 个节点的树，有 \(m\) 次询问，每次询问给定 \((l,r,x)\)，表示询问

\[ \sum_{i=l}^{r}{dep\big[\operatorname{lca}(i,x)\big]} \]

先对查询进行差分，转换成前缀的查询，然后我们就可以对节点编号进行扫描线。

利用 \(dep\) 的性质，我们有简单的做法。考虑 \(y\) 对 \(x\) 的贡献，我们可以对 \(1\to y\) 的链加一，然后直接查询 \(1\to x\) 链的权值和，就是 \(dep\big[\operatorname{lca}(x,y)\big]\)。

代码

#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;
const int N = 5e4 + 10;
const int MOD = 201314;

struct Edge {
    int v, next;
} pool[2 * N];
int ne, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

struct Op {
    int p, z, w, id;
    inline Op(int _p, int _z, int _w, int _id) { p = _p, z = _z, w = _w, id = _id; }
    inline bool operator<(const Op &b) const {
        if(p != b.p) return p < b.p;
        return id < b.id;
    }
};

vector<Op> op;

int n, m;
ll ans[N];

int sz[N], son[N], fa[N];
int dfn[N], id[N], dt;
int top[N];

namespace BIT {
    ll sum[N][2];
    inline int lowbit(int x) { return x & -x; }
    inline void add(int p, ll v) {
        for(int i = p + 2; i <= n + 4; i += lowbit(i)) {
            (sum[i][0] += v) %= MOD;
            (sum[i][1] += p * v) %= MOD;
        }
    }
    inline void add(int l, int r, ll v) {
        add(r + 1, -v);
        add(l, v);
    }
    inline ll query(int p) {
        ll res = 0;
        for(int i = p + 2; i > 0; i -= lowbit(i)) {
            (res += ((p + 1) * sum[i][0] % MOD - sum[i][1]) % MOD + MOD) %= MOD;
        }
        return res;
    }
    inline ll query(int l, int r) {
        return (query(r) - query(l - 1) + MOD) % MOD;
    }
}

void dfs1(int u, int a0) {
    fa[u] = a0;
    sz[u] = 1;
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v;
        dfs1(v, u);
        sz[u] += sz[v];
        if(sz[v] > sz[son[u]]) son[u] = v;
    }
}

void dfs2(int u, int tp) {
    dfn[u] = ++dt;
    id[dt] = u;
    top[u] = tp;
    if(!son[u]) return;
    dfs2(son[u], tp);
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v;
        if(v == son[u]) continue;
        dfs2(v, v);
    }
}

void add(int p, int v) {
    while(p) {
        BIT::add(dfn[top[p]], dfn[p], 1);
        p = fa[top[p]];
    }
}

ll query(int p) {
    ll res = 0;
    while(p) {
        (res += BIT::query(dfn[top[p]], dfn[p])) %= MOD;
        p = fa[top[p]];
    }
    return res;
}

int main() {

    cin >> n >> m;
    for(int i = 2, x; i <= n; i++) {
        cin >> x;
        ++x;
        addEdge(x, i);
    }
    for(int i = 1; i <= m; i++) {
        int l, r, z;
        cin >> l >> r >> z;
        ++l, ++r, ++z;
        if(l > 1) op.push_back((Op){l - 1, z, -1, i});
        op.push_back((Op){r, z, 1, i});
    }

    for(int i = 1; i <= n; i++) op.push_back((Op){i, 0, 0, 0});

    sort(op.begin(), op.end());

    dfs1(1, 0);
    dfs2(1, 1);

    for(Op &o : op) {
        if(o.id) {
            (ans[o.id] += query(o.z) * o.w % MOD + MOD) %= MOD;
        } else {
            add(o.p, 1);
        }
    }

    for(int i = 1; i <= m; i++) cout << ans[i] << '\n';

    return 0;
}

P3345 [ZJOI2015] 幻想乡战略游戏

题意

给定一棵 \(n\) 个节点的无根树，点有点权，边有边权。有 \(q\) 次修改，每次修改会修改一个节点的点权，然后立即询问树的加权重心以及加权深度和。

\(n,q\le 10^5\)

先考虑如何找到加权重心。重心的位置显然和边权无关。考虑重心的一个定义：

最深的满足 \(sz[x]\ge \lceil\frac{n}{2}\rceil\) 的节点。

容易发现，满足 \(sz[x]\ge \lceil\frac{n}{2}\rceil\) 的 \(x\) 分布在一条根链上，因此 dfn 序随深度增加而增加。使用树剖维护 sz，线段树上二分即可。

然后考虑怎么求加权深度和。推一下式子：

\[ \begin{align*} \sum_{x=1}^n{dis(rt,x)\times a_x}&=\sum_{x=1}^n{a_x\times \Big(dis(rt)+dis(x)-2dis\big(\operatorname{lca}(rt,x)\big)\Big)}\\ &=\sum_{x=1}^{n}a_xdis(x)+dis(rt)\sum_{x=1}^{n}a_x-2\sum_{x=1}^{n}a_xdis\big(\operatorname{lca}(x, rt)\big) \end{align*} \]

其中 \(dis(1,x)\) 省略为 \(dis(x)\)。前两项都是平凡的。第三项利用上一题的技巧，我们给 \(x\) 的根链上的每个点 \(y\) 都加上 \(a_x\times w\big(fa[y], y\big)\)，查询 \(rt\) 的根链权值和就是第三项的值。

代码

#include<iostream>
#define int long long
using namespace std;
const int N = 1e5 + 10;

struct Edge {
    int v, w, next;
} pool[2 * N];
int ne, head[N];

void addEdge(int u, int v, int w) {
    pool[++ne] = {v, w, head[u]};
    head[u] = ne;
}

int n, q;

int dep[N], d[N], sz[N], son[N], fa[N];
int dfn[N], id[N], dt;
int top[N];

int fw[N], sfw[N];

void dfs1(int u) {
    sz[u] = 1;
    dep[u] = dep[fa[u]] + 1;
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v, w = pool[e].w;
        if(v == fa[u]) continue;
        fa[v] = u;
        d[v] = d[u] + w;
        fw[v] = w;
        dfs1(v);
        sz[u] += sz[v];
        if(sz[v] > sz[son[u]]) son[u] = v;
    }
}

void dfs2(int u, int tp) {
    dfn[u] = ++dt;
    id[dt] = u;
    top[u] = tp;
    if(son[u]) dfs2(son[u], tp);
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

namespace SegT {
    int mx[4 * N], tag[4 * N], sum[4 * N];
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    inline void push_up(int p) {
        mx[p] = max(mx[lc(p)], mx[rc(p)]);
        sum[p] = sum[lc(p)] + sum[rc(p)];
    }
    inline void move_tag(int p, int l, int r, int tg) {
        mx[p] += tg;
        tag[p] += tg;
        sum[p] += (sfw[r] - sfw[l - 1]) * tg;
    }
    inline void push_down(int p, int l, int r, int mid) {
        if(!tag[p]) return;
        move_tag(lc(p), l, mid, tag[p]);
        move_tag(rc(p), mid + 1, r, tag[p]);
        tag[p] = 0;
    }
    inline void add(int p, int l, int r, int ql, int qr, int v) {
        if(ql <= l && r <= qr) {
            move_tag(p, l, r, v);
            return;
        }
        int mid = (l + r) >> 1;
        push_down(p, l, r, mid);
        if(ql <= mid) add(lc(p), l, mid, ql, qr, v);
        if(mid < qr) add(rc(p), mid + 1, r, ql, qr, v);
        push_up(p);
    }
    inline int query(int p, int l, int r, int lim) {
        if(l == r) return l;
        int mid = (l + r) >> 1;
        push_down(p, l, r, mid);
        if(mx[rc(p)] >= lim) return query(rc(p), mid + 1, r, lim);
        return query(lc(p), l, mid, lim);
    }
    inline int query_sum(int p, int l, int r, int ql, int qr) {
        if(ql <= l && r <= qr) return sum[p];
        int mid = (l + r) >> 1;
        push_down(p, l, r, mid);
        if(qr <= mid) return query_sum(lc(p), l, mid, ql, qr);
        if(mid < ql) return query_sum(rc(p), mid + 1, r, ql, qr);
        return query_sum(lc(p), l, mid, ql, qr) + query_sum(rc(p), mid + 1, r, ql, qr);
    }
}

int sv, sd;

void add(int p, int v) {
    sv += v;
    sd += d[p] * v;
    while(p) {
        SegT::add(1, 1, n, dfn[top[p]], dfn[p], v);
        p = fa[top[p]];
    }
}

int query(int p) {
    int res = 0;
    while(p) {
        res += SegT::query_sum(1, 1, n, dfn[top[p]], dfn[p]);
        p = fa[top[p]];
    }
    return res;
}

signed main() {

    cin >> n >> q;
    for(int i = 1; i <= n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w);
    }

    dfs1(1);
    dfs2(1, 1);

    for(int i = 1; i <= n; i++) sfw[i] = sfw[i - 1] + fw[id[i]];

    while(q--) {
        int x, y;
        cin >> x >> y;
        add(x, y);
        int cen = id[SegT::query(1, 1, n, (sv + 1) / 2)];
        int res = sd + sv * d[cen] - 2 * query(cen);
        cout << res << '\n';
    }

    return 0;
}