Author: lllyouo
Date: 20251014
tag: 树上问题, 树链剖分
link: https://www.luogu.com.cn/problem/P2590

问题描述

link

分析

略

参考代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 10;

struct SegmentTree {
    int l, r, dat, val;
} t[N * 4];

int fa[N], dep[N], siz[N], son[N], top[N], dfn[N], dfn_cnt, rnk[N];
int h[N], e[2 * N], ne[2 * N], idx;
int n, m, a[N];

void add(int x, int y) {
    e[idx] = y, ne[idx] = h[x], h[x] = idx++;
}

void pushup(int p) {
    t[p].dat = t[p << 1].dat + t[p << 1 | 1].dat;
    t[p].val = max(t[p << 1].val, t[p << 1 | 1].val);
}

void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if (l == r) {
        t[p].dat = rnk[l];
        t[p].val = rnk[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    pushup(p);
}

void modify(int p, int x, int v) {
    if (t[p].l == x && t[p].r == x) {
        t[p].dat = v;
        t[p].val = v;
        return;
    }
    int mid = (t[p].l + t[p].r) >> 1;
    if (x <= mid)
        modify(p << 1, x, v);
    else
        modify(p << 1 | 1, x, v);
    pushup(p);
}

int query(int p, int l, int r) {
    if (t[p].l >= l && t[p].r <= r) return t[p].dat;

    int mid = (t[p].l + t[p].r) >> 1;
    int ans = 0;
    if (l <= mid) ans += query(p << 1, l, r);
    if (r > mid) ans += query(p << 1 | 1, l, r);
    return ans;
}

int query_max(int p, int l, int r) {
    if (t[p].l >= l && t[p].r <= r) return t[p].val;

    int mid = (t[p].l + t[p].r) >> 1;
    int ans = -1e9;
    if (l <= mid) ans = max(ans, query_max(p << 1, l, r));
    if (r > mid) ans = max(ans, query_max(p << 1 | 1, l, r));
    return ans;
}

void dfs1(int u, int f) {
    fa[u] = f, dep[u] = dep[f] + 1, siz[u] = 1;

    for (int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        if (v == f) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[son[u]]) son[u] = v;
    }
}

void dfs2(int u, int ftop) {
    top[u] = ftop, dfn[u] = ++dfn_cnt, rnk[dfn_cnt] = a[u];

    if (son[u]) dfs2(son[u], ftop); // 存在重儿子则深入

    for (int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        if (v != son[u] && v != fa[u]) dfs2(v, v); // 存在轻儿子则深入
    }
}

int query_path(int x, int y) {
    int ans = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        ans += query(1, dfn[top[x]], dfn[x]);
        x = fa[top[x]];
    }
    if (dep[x] < dep[y]) swap(x, y);
    ans += query(1, dfn[y], dfn[x]);
    return ans;
}

int query_path_max(int x, int y) {
    int ans = -1e9;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        ans = max(ans, query_max(1, dfn[top[x]], dfn[x]));
        x = fa[top[x]];
    }
    if (dep[x] < dep[y]) swap(x, y);
    ans = max(ans, query_max(1, dfn[y], dfn[x]));
    return ans;
}

signed main() {
    cin >> n;

    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        add(x, y), add(y, x);
    }

    for (int i = 1; i <= n; i++) cin >> a[i];

    cin >> m;

    dfs1(1, 0);
    dfs2(1, 1);
    build(1, 1, n);

    while (m--) {
        string op; cin >> op;
        int x, y, z;
        if (op == "CHANGE") {
            cin >> x >> z;
            modify(1, dfn[x], z);
        } else if (op == "QSUM") {
            cin >> x >> y;
            cout << query_path(x, y) << endl;
        } else {
            cin >> x >> y;
            cout << query_path_max(x, y) << endl;
        }
    }

    return 0;
}