「HAOI2015」树上操作 - 树链剖分 + DFS序

有一棵点数为 的树，以点 为根，且树点有边权。然后有 个操作，分为三种：

1. 把某个节点 的点权增加 。
2. 把某个节点 为根的子树中所有点的点权都增加 。
3. 询问某个节点 到根的路径中所有点的点权和。

链接

BZOJ 4034
COGS 1963

题解

裸树剖 + DFS 序，注意要开 long long，要不然和暴力分一样 ……

代码

#include <cstdio>
#include <stack>

const int MAXN = 100000;
const int MAXM = 100000;

struct Node;
struct Edge;
struct Path;

struct Node {
    Edge *e;
    Node *c, *p;
    int size, pos, posEnd;
    bool visited;
    Path *path;
} N[MAXN];

struct Edge {
    Node *s, *t;
    Edge *next;

    Edge(Node *s, Node *t) : s(s), t(t), next(s->e) {}
};

inline void addEdge(const int u, const int v) {
    N[u].e = new Edge(&N[u], &N[v]);
    N[v].e = new Edge(&N[v], &N[u]);
}

struct SegmentTree {
    int l, r;
    SegmentTree *lc, *rc;
    long long value, lazy;

    SegmentTree(const int l, const int r, SegmentTree *lc, SegmentTree *rc) : l(l), r(r), lc(lc), rc(rc), value(0), lazy(0) {}

    void cover(const long long delta) { value += delta * (r - l + 1), lazy += delta; }

    void pushDown() {
        if (lazy) {
            if (lc) lc->cover(lazy);
            if (rc) rc->cover(lazy);
            lazy = 0;
        }
    }

    void update(const int l, const int r, const long long delta) {
        if (l > this->r || r < this->l) return;
        else if (l <= this->l && r >= this->r) cover(delta);
        else {
            pushDown();
            value = 0;
            if (lc) lc->update(l, r, delta), value += lc->value;
            if (rc) rc->update(l, r, delta), value += rc->value;
        }
    }

    long long query(const int l, const int r) {
        if (l > this->r || r < this->l) return 0;
        else if (l <= this->l && r >= this->r) return value;
        else {
            pushDown();
            long long result = 0;
            if (lc) result += lc->query(l, r);
            if (rc) result += rc->query(l, r);
            return result;
        }
    }
} *segment;

SegmentTree *buildSegmentTree(const int l, const int r) {
    if (l > r) return NULL;
    else if (l == r) return new SegmentTree(l, r, NULL, NULL);
    else return new SegmentTree(l, r, buildSegmentTree(l, l + ((r - l) >> 1)), buildSegmentTree(l + ((r - l) >> 1) + 1, r));
}

struct Path {
    Node *top;

    Path(Node *top) : top(top) {}
};

int n, m;
long long a[MAXN];

inline void cut() {
    std::stack<Node *> s;
    s.push(&N[0]);

    while (!s.empty()) {
        Node *v = s.top();
        if (!v->visited) {
            v->visited = true;
            for (Edge *e = v->e; e; e = e->next) if (e->t->p == NULL && e->t != v->p) e->t->p = v, s.push(e->t);
        } else {
            v->size = 1;
            for (Edge *e = v->e; e; e = e->next) if (e->t->p == v) {
                v->size += e->t->size;
                if (v->c == NULL || v->c->size < e->t->size) v->c = e->t;
            }

            s.pop();
        }
    }

    for (int i = 0; i < n; i++) N[i].visited = false;

    s.push(&N[0]);
    int time = -1;
    while (!s.empty()) {
        Node *v = s.top();
        if (!v->visited) {
            v->visited = true;
            v->pos = ++time;

            if (!v->p || v != v->p->c) v->path = new Path(v);
            else v->path = v->p->path;

            for (Edge *e = v->e; e; e = e->next) if (e->t->p == v && e->t != v->c) s.push(e->t);
            if (v->c) s.push(v->c);
        } else v->posEnd = time, s.pop();
    }

    segment = buildSegmentTree(0, n - 1);
    for (int i = 0; i < n; i++) segment->update(N[i].pos, N[i].pos, a[i]);
}

inline long long queryToRoot(const int x) {
    Node *v = &N[x];
    long long sum = 0;
    while (v) {
        sum += segment->query(v->path->top->pos, v->pos);
        v = v->path->top->p;
    }
    return sum;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
    for (int i = 0, u, v; i < n - 1; i++) scanf("%d %d", &u, &v), u--, v--, addEdge(u, v);

    cut();

    for (int i = 0, cmd; i < m; i++) {
        scanf("%d", &cmd);
        if (cmd == 1) {
            int x, a;
            scanf("%d %d", &x, &a), x--;
            segment->update(N[x].pos, N[x].pos, a);
        } else if (cmd == 2) {
            int x, a;
            scanf("%d %d", &x, &a), x--;
            segment->update(N[x].pos, N[x].posEnd, a);
        } else if (cmd == 3) {
            int x;
            scanf("%d", &x), x--;
            printf("%lld\n", queryToRoot(x));
        }
    }

    return 0;
}