HDU3669 Aragorn's Story 树链剖分 点权

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=3966

题意：

n个点的，m条边，每个点都 有点权

修改 从u->v上所有点的点权

查询单点点权

题解：

树链剖分裸题

树链剖分就是将树分割为多条边，然后利用数据结构来维护这些链的一个技巧

• 重儿子：父亲节点的所有儿子中子树结点数目最多（ sizesiz**e 最大）的结点；
• 轻儿子：父亲节点中除了重儿子以外的儿子；
• 重边：父亲结点和重儿子连成的边；
• 轻边：父亲节点和轻儿子连成的边；
• 重链：由多条重边连接而成的路径；
• 轻链：由多条轻边连接而成的路径；

1.求出子树大小和每个点的重儿子，处理sz数组，son数组，fa数组和dep数组

2.连接重链，记录dfs序，每个链的顶端节点，处理出rank数组，top数组，id数组

3.维护链上信息

代码：

#include <set>

#include <map>

#include <cmath>

#include <cstdio>

#include <string>

#include <vector>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long LL;

typedef pair<int, int> pii;

typedef unsigned long long uLL;

#define ls rt<<1

#define rs rt<<1|1

#define lson l,mid,rt<<1

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

#define bug printf("*********\n")

#define FIN freopen("input.txt","r",stdin);

#define FON freopen("output.txt","w+",stdout);

#define IO ios::sync_with_stdio(false),cin.tie(0)

#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n"

#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"

#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"

const int maxn = 3e5 + 5;

const int INF = 0x3f3f3f3f;

int n, m, Q;

int a[maxn], sz[maxn], dep[maxn], fa[maxn], top[maxn], id[maxn], son[maxn], Rank[maxn];

int sum[maxn << 2], lazy[maxn << 2];

struct EDGE {

    int u, v, nt;

} edge[maxn << 1];

int head[maxn], summ, cnt;

void add_edge(int u, int v) {

    edge[++summ].u = u; edge[summ].v = v; edge[summ].nt = head[u]; head[u] = summ;

}

void dfs1(int u) {

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

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

        int v = edge[i].v;

        if (v != fa[u]) {

            fa[v] = u;

            dep[v] = dep[u] + 1;

            dfs1(v);

            sz[u] += sz[v];

            if (sz[v] > sz[son[u]]) son[u] = v;

        }

    }

}

void dfs2(int u, int tp, int x) {

    top[u] = tp; id[u] = ++cnt; Rank[cnt] = u;

    if (son[u]) dfs2(son[u], tp, 1);

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

        int v = edge[i].v;

        if (v == son[u] || v == fa[u]) continue;

        dfs2(v, v, 2);

    }

}

void init() {

    memset(head, -1, sizeof(head));

    summ = 1; cnt = 0;

    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

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

        int u, v;

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

        add_edge(u, v); add_edge(v, u);

    }

    dep[1] = 1; fa[1] = 0;

    dfs1(1);

    dfs2(1, 1, 1);

}

void pushup(int rt) {

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

}

void pushdown(int rt, int mid) {

    if (lazy[rt]) {

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

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

        sum[rt << 1] += lazy[rt] * (mid - mid / 2);

        sum[rt << 1 | 1] += lazy[rt] * (mid / 2);

        lazy[rt] = 0;

    }

}

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

    lazy[rt] = 0;

    if (l == r) {

        sum[rt] = a[Rank[l]];

        return;

    }

    int mid = (l + r) >> 1;

    build(lson);

    build(rson);

    pushup(rt);

}

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

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

        sum[rt] += val * (r - l + 1);

        lazy[rt] += val;

        return;

    }

    pushdown(rt, r - l + 1);

    int mid = (l + r) >> 1;

    if (L <= mid) update(L, R, val, lson);

    if (mid < R) update(L, R, val, rson);

    pushup(rt);

}

int query(int pos, int l, int r, int rt) {

    if (l == r) {

        return sum[rt];

    }

    pushdown(rt, r - l + 1);

    int mid = (l + r) >> 1;

    if (pos <= mid) return query(pos, lson);

    if (mid < pos) return query(pos, rson);

}

void change(int x, int y, int val) {

    while (top[x] != top[y]) {

        if (dep[top[x]] < dep[top[y]]) std::swap(x, y);

        update(id[top[x]], id[x], val, 1, n, 1);

        x = fa[top[x]];

    }

    if (dep[x] > dep[y]) std::swap(x, y);

    update(id[x], id[y], val, 1, n, 1);

}

int main() {

#ifndef ONLINE_JUDGE

    FIN

#endif

    while (~scanf("%d %d %d", &n, &m, &Q)) {

        init();

        build(1, n, 1);

        while (Q--) {

            char s[2];

            int x, y, z;

            scanf("%s", s);

            if (s[0] == 'I') {

                scanf("%d %d %d", &x, &y, &z);

                change(x, y, z);

            }

            if (s[0] == 'D') {

                scanf("%d %d %d", &x, &y, &z);

                change(x, y, -z);

            }

            if (s[0] == 'Q') {

                scanf("%d", &x);

                printf("%d\n", query(id[x], 1, n, 1));

            }

        }

    }

}