spoj - Grass Planting（树链剖分模板题）

Grass Planting

题意

给出一棵树，树有边权。每次给出节点 (u, v) ，有两种操作：1. 把 u 到 v 路径上所有边的权值加 1。2. 查询 u 到 v 的权值之和。

分析

如果这些值不是在树上，而是在区间上，那么凭借线段树、树状数组可以很轻松的解决，但是在树上则不能直接操作。

树链剖分就是将树上的节点映射到区间上，从而实现区间操作。

学习树链剖分前需要掌握的知识点：线段树、LCA。

参考blog

认真读完这篇 blog ，跟着算法流程走一遍差不多就懂了。

code

#include<bits/stdc++.h>

#define lson l, m, rt << 1

#define rson m + 1, r, rt << 1 | 1

using namespace std;

typedef long long ll;

const int MAXN = 2e5 + 10;

int n, m;

int fa[MAXN]; // fa[v]: v 的父亲

int dep[MAXN]; // dep[v]: v 的深度（根深度为１）

int siz[MAXN]; // : 以 v 为根的子树的节点数

int son[MAXN]; // : 重儿子，siz[u] 为 v　的子节点中 siz　值最大的，那么 u 就是 v 的重儿子

int top[MAXN]; // : 表示 v 所在的重链的顶端节点

int w[MAXN]; // : 表示 v 与其父亲节点的连边在线段树中的位置

int num; // 将树映射到线段树上的标号

int cnt, head[MAXN];

struct Edge {

    int to, next;

}edge[MAXN];

void addedge(int u, int v) {

    edge[cnt].to = v;

    edge[cnt].next = head[u];

    head[u] = cnt++;

}

void dfs(int u) {

    siz[u] = 1; son[u] = 0;

    for(int i = head[u]; ~i; i = edge[i].next) {

        if(edge[i].to != fa[u]) {

            fa[edge[i].to] = u;

            dep[edge[i].to] = dep[u] + 1;

            dfs(edge[i].to);

            if(siz[edge[i].to] > siz[son[u]]) son[u] = edge[i].to;

            siz[u] += siz[edge[i].to];

        }

    }

}

void build_tree(int u, int tp) {

    w[u] = ++num; top[u] = tp;

    if(son[u]) build_tree(son[u], top[u]); // 使重链各边在线段树中呈连续分布

    for(int i = head[u]; ~i; i = edge[i].next) {

        int v = edge[i].to;

        if(v != son[u] && v != fa[u])

            build_tree(v, v);

    }

}

ll sum[MAXN], add[MAXN];

void pushUp(int rt) {

    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];

}

void pushDown(int rt, int m) {

    if(add[rt]) {

        add[rt << 1] += add[rt];

        add[rt << 1 | 1] += add[rt];

        sum[rt << 1] += (m - (m >> 1)) * add[rt];

        sum[rt << 1 | 1] += (m >> 1) * add[rt];

        add[rt] = 0;

    }

}

void build(int l, int r, int rt) {

    add[rt] = sum[rt] = 0;

    if(l == r) return;

    int m = (l + r) / 2;

    build(lson); build(rson);

}

void update(int L, int R, int l, int r, int rt) {

    if(L <= l && R >= r) {

        sum[rt] += r - l + 1;

        add[rt] += 1;

        return;

    }

    pushDown(rt, r - l + 1);

    int m = (l + r) / 2;

    if(m >= L) update(L, R, lson);

    if(m < R) update(L, R, rson);

    pushUp(rt);

}

ll query(int L, int R, int l, int r, int rt) {

    if(L <= l && R >= r) return sum[rt];

    pushDown(rt, r - l + 1);

    int m = (l + r) / 2;

    ll res = 0;

    if(m >= L) res += query(L, R, lson);

    if(m < R) res += query(L, R, rson);

    return res;

}

void change(int v, int u) {

    int t1 = top[v], t2 = top[u];

    while(t1 != t2) {

        if(dep[t1] < dep[t2]) {

            swap(t1, t2); swap(v, u);

        }

        update(w[t1], w[v], 1, n, 1);

        v = fa[t1]; t1 = top[v];

    }

    if(v == u) return;

    if(dep[v] > dep[u]) swap(v, u);

    update(w[son[v]], w[u], 1, n, 1);

}

ll seek(int v, int u) {

    int t1 = top[v], t2 = top[u];

    ll res = 0;

    while(t1 != t2) {

        if(dep[t1] < dep[t2]) {

            swap(t1, t2); swap(v, u);

        }

        res += query(w[t1], w[v], 1, n, 1);

        v = fa[t1]; t1 = top[v];

    }

    if(v == u) return res;

    if(dep[v] > dep[u]) swap(v, u);

    return res + query(w[son[v]], w[u], 1, n, 1);

}

int main() {

    memset(head, -1, sizeof head);

    cnt = num = 0;

    scanf("%d%d", &n, &m);

    for(int i = 1;  i < n; i++) {

        int u, v;

        scanf("%d%d", &u, &v);

        addedge(u, v);

        addedge(v, u);

    }

    dfs(1);

    build_tree(1, 1);

    build(1, n, 1);

    while(m--) {

        char cc[2];

        int u, v;

        scanf("%s%d%d", cc, &u, &v);

        if(cc[0] == 'P') change(u, v);

        else printf("%lld\n", seek(u, v));

    }

    return 0;

}