[HAOI2015]树上操作 题解

做法

关于树链剖分我也不知道该怎么讲了，有许多博客比我讲得好，如果你是还没有学习树链剖分的同学的话，在这里安利博客：

OIWIKI

神佬的博客

（这里指的是轻重链剖分）

这里总结一下：

适用情况

• 对于一条路径上的值进行修改

• 查询一条路径上的一些具有可以进行区间维护的性质的东西(比如求和，最大值)

额外的例子:

查询一条路径中的元素种类总数

查询一条路径中大于一个给定的值的数的个数(树链剖分后套权值线段树 or 主席树)

查询路径中第大的数

• 对于一棵子树中的值进行修改

• 查询一棵子树中的一些具有可以进行区间维护的性质的东西(比如求和，最大值)

上面四种是最裸的树链剖分。直接上树链剖分加线段树即可。

算法复杂度：

对于路径上的更新权值/求和的时间复杂度是O()。

因为重链的条数不超过条(一般的话数量可能远远低于这个值)，每次线段树维护的时间复杂度是:O()的，所以时间复杂度是O的。

子树修改/查询时间复杂度:O，很明显，因为后编号是连续的，时间复杂度就是线段树做区间查询/修改的复杂度

如何构造一棵树使得轻重链剖分后重链条数达到

完全二叉树即可。你可以自己画一棵完全二叉树，然后你就会发现重链很多，但是因为是完全二叉树，那它的深度也不会很深，所以基本上卡不死轻重链剖分。

因为这是一篇题解，所以放上这一题的代码吧。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, root, m, now = 0;
int start[100005], dfn_id[100005];
struct tree {
    int siz, son;
    int data, fa;
    int deep, dfn, tp;
    int rs;
} node[100005];
struct Tree {
    int l, r, sum, laz;
} T[500005];
struct road {
    int u, v;
} r[500005];
int DFS1(int x, int from) {
    node[x].deep = node[from].deep + 1;
    node[x].siz = 1, node[x].son = 0;
    node[x].fa = from;
    for (int i = start[x]; i <= m && r[i].u == x; i++) {
        int to = r[i].v;
        if (!node[to].deep) {
            int v;
            v = DFS1(to, x);
            if (v > node[node[x].son].siz)
                node[x].son = to;
            node[x].siz += v;
        }
    }
    return node[x].siz;
}
int DFS2(int x, int top) {
    node[x].tp = top;
    node[x].dfn = ++now;
    dfn_id[now] = x;
    node[x].rs = now;
    if (node[x].son != 0)
        node[x].rs = max(DFS2(node[x].son, top), node[x].rs);
    for (int i = start[x]; i <= m && r[i].u == x; i++) {
        int to = r[i].v;
        if (!node[to].dfn && to != node[x].fa && to != node[x].son)
            node[x].rs = max(DFS2(to, to), node[x].rs);
    }
    return node[x].rs;
}
void build_tree(int x, int l, int r) {
    T[x].l = l, T[x].r = r;
    T[x].laz = 0;
    if (T[x].l == T[x].r) {
        T[x].sum = node[dfn_id[l]].data;
        return;
    }
    int mid = (l + r) >> 1;
    build_tree(x << 1, l, mid);
    build_tree(x << 1 | 1, mid + 1, r);
    T[x].sum = T[x << 1].sum + T[x << 1 | 1].sum;
}
int cmp(road A, road B) { return A.u < B.u; }
void ad(int x, int k) {
    T[x].sum += (T[x].r - T[x].l + 1) * k;
    T[x].laz += k;
}
int pushdown(int x) {
    if (T[x].laz == 0)
        return 0;
    ad(x << 1, T[x].laz);
    ad(x << 1 | 1, T[x].laz);
    T[x].laz = 0;
    return 0;
}
int change(int x, int l, int r, int k) {
    if (T[x].l >= l && T[x].r <= r) {
        ad(x, k);
        return 0;
    }
    pushdown(x);
    int mid = (T[x].l + T[x].r) >> 1;
    if (l <= mid)
        change(x << 1, l, r, k);
    if (r > mid)
        change(x << 1 | 1, l, r, k);
    T[x].sum = T[x << 1].sum + T[x << 1 | 1].sum;
    return 0;
}
int get(int x, int l, int r) {
    int ans = 0;
    if (T[x].l >= l && T[x].r <= r)
        return T[x].sum;
    pushdown(x);
    int mid = (T[x].l + T[x].r) >> 1;
    if (l <= mid)
        ans += get(x << 1, l, r);
    if (r > mid)
        ans += get(x << 1 | 1, l, r);
    return ans;
}
void dealsum(int x, int y) {
    int ans = 0;
    while (node[x].tp != node[y].tp) {
        int fx = node[x].tp, fy = node[y].tp;
        if (node[fx].deep < node[fy].deep)
            swap(fx, fy), swap(x, y);
        ans += get(1, node[fx].dfn, node[x].dfn);
        x = node[fx].fa;
    }
    if (node[x].dfn > node[y].dfn)
        ans += get(1, node[y].dfn, node[x].dfn);
    else
        ans += get(1, node[x].dfn, node[y].dfn);
    cout << ans << endl;
}
signed main() {
    int Q;
    cin >> n >> Q;
    root = 1;
    int ls = -1;
    for (int i = 1; i <= n; i++) cin >> node[i].data;
    for (int i = 1; i <= n - 1; i++) {
        cin >> r[i].u >> r[i].v;
        r[i + n - 1] = r[i];
        swap(r[i + n - 1].u, r[i + n - 1].v);
    }
    m = (n - 1) << 1;
    sort(r + 1, r + 1 + m, cmp);
    for (int i = 1; i <= m; i++)
        if (ls != r[i].u)
            ls = r[i].u, start[ls] = i;
    DFS1(root, 0);
    DFS2(root, root);
    build_tree(1, 1, n);
    for (int i = 1; i <= Q; i++) {
        int op, l, r, z;
        cin >> op;
        if (op == 1) {
            cin >> l >> z;
            change(1, node[l].dfn, node[l].dfn, z);
        }
        if (op == 2) {
            cin >> l >> z;
            change(1, node[l].dfn, node[l].rs, z);
        }
        if (op == 3) {
            cin >> l;
            dealsum(1, l);
        }
    }
    return 0;
}