Portal

Portal1: BZOJ

Portal2: Luogu

Description

一棵树上有$n$个节点，编号分别为$1$到$n$，每个节点都有一个权值$w$。

我们将以下面的形式来要求你对这棵树完成一些操作：

• CHANGE u t： 把结点$u$的权值改为$t$；

• QMAX u v： 询问从点$u$到点$v$的路径上的节点的最大权值；

• QSUM u v： 询问从点$u$到点$v$的路径上的节点的权值和。

注意：从点$u$到点$v$的路径上的节点包括$u$和$v$本身。

Input

输入文件的第一行为一个整数$n$，表示节点的个数。

接下来$n – 1$行，每行$2$个整数$a$和$b$，表示节点$a$和节点$b$之间有一条边相连。

接下来一行$n$个整数，第i个整数$w_i$表示节点$i$的权值。

接下来$1$行，为一个整数$q$，表示操作的总数。

接下来$q$行，每行一个操作，以CHANGE u t或者QMAX u v或者QSUM u v的形式给出。

Output

对于每个QMAX或者QSUM的操作，每行输出一个整数表示要求输出的结果。

Sample Input

4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4

Sample Output

4
1
2
2
10
6
5
6
5
16

Solution

同『题解』洛谷P3384 【模板】树链剖分。

Code

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

const int INF = 0x3f3f3f3f, MAXN = 400005;
struct EDGE {
    int u, v, nxt;
} edge[MAXN];
struct node {
    int l, r, w, Max, size, f;
} tree[MAXN];
int n, m, cnt, tot, a[MAXN], b[MAXN], son[MAXN], top[MAXN], idx[MAXN], dep[MAXN], head[MAXN], father[MAXN];
inline void addedge(int u, int v) {
    edge[++tot].u = u; edge[tot].v = v; edge[tot].nxt = head[u]; head[u] = tot;
}
inline void dfs1(int x, int y) {//预处理
    tree[x].size = 1;
    for (int i = head[x]; ~i; i = edge[i].nxt) {
        int v = edge[i].v;
        if (v == y) continue;
        dep[v] = dep[x] + 1;
        father[v] = x;
        dfs1(v, x);
        tree[x].size += tree[v].size;
        if (tree[v].size > tree[son[x]].size) son[x] = v;
    }
}
inline void dfs2(int now, int topf) {//预处理
    idx[now] = ++cnt;
    a[cnt] = now;
    top[now] = topf;
    if (son[now]) dfs2(son[now], topf);
    for (int i = head[now]; ~i; i = edge[i].nxt) {
        int v = edge[i].v;
        if (v == father[now] || v == son[now]) continue;
        dfs2(v, v);
    }
}
inline void pushup(int root) {
    tree[root].w = tree[root << 1].w + tree[root << 1 | 1].w;
    tree[root].Max = max(tree[root << 1].Max , tree[root << 1 | 1].Max);
}
inline void build(int root, int l, int r) {
    if (l == r) {
        tree[root].w = tree[root].Max = b[a[l]];
        return ;
    }
    int mid = l + r >> 1;
    build(root << 1, l, mid);
    build(root << 1 | 1, mid + 1, r);
    pushup(root);
}
inline void update(int root, int l, int r, int pos, int val) {
    int mid = l + r >> 1;
    if (l == r) {
        tree[root].w = tree[root].Max = val;
        return ;
    }
    if (pos <= mid) update(root << 1, l, mid, pos, val); else update(root << 1 | 1, mid + 1, r, pos, val);
    pushup(root);
}
inline int query_sum(int root, int l, int r, int ansl, int ansr) {
    int mid = l + r >> 1, ret = 0;
    if (ansl <= l && r <= ansr) return tree[root].w;
    if (ansl <= mid) ret += query_sum(root << 1, l, mid, ansl, ansr);
    if (ansr > mid) ret += query_sum(root << 1 | 1, mid + 1, r, ansl, ansr);
    pushup(root);
    return ret;
}
inline int query_max(int root, int l, int r, int ansl, int ansr) {
    int mid = l + r >> 1, ret = -INF;
    if (ansl <= l && r <= ansr) return tree[root].Max;
    if (ansl <= mid) ret = max(ret, query_max(root << 1, l, mid, ansl, ansr));
    if (ansr > mid) ret = max(ret, query_max(root << 1 | 1, mid + 1, r, ansl, ansr));
    pushup(root);
    return ret;
}
inline int tree_sum(int x, int y) {//树上求和
    int ret = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        ret += query_sum(1, 1, n, idx[top[x]], idx[x]);
        x = father[top[x]];
    }
    if (dep[x] < dep[y]) swap(x, y);
    ret += query_sum(1, 1, n, idx[y], idx[x]);
    return ret;
}
inline int tree_max(int x, int y) {//树上求最大值
    int ret = -INF;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        ret = max(ret , query_max(1, 1, n, idx[top[x]], idx[x]));
        x = father[top[x]];
    }
    if (dep[x] < dep[y]) swap(x, y);
    ret = max(ret, query_max(1, 1, n, idx[y], idx[x]));
    return ret;
}
int main() {
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        addedge(x, y);
        addedge(y, x);
    }
    for (int i = 1; i <= n; i++)
        scanf("%d", &b[i]);
    dep[1] = 1;
    father[1] = 1;
    dfs1(1, -1);
    dfs2(1, 1);
    build(1, 1, n);
    scanf("%d", &m);
    while (m--) {
        int opt, x, y, val;
        char s[6];
        scanf("%s%d%d", s, &x, &y);
        if (s[0] == 'C') update(1, 1, n, idx[x], y); else
        if (s[0] == 'Q' && s[1] == 'M') printf("%d\n", tree_max(x, y)); else printf("%d\n", tree_sum(x, y));
    }
    return 0;
}

Attachment

测试数据下载：https://www.lanzous.com/i5182ne