树的统计

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 3488 字
树上单点修改权值，查询任意两点路径上节点的权
一本通
例
正文

/*
原题：T1560 「一本通 4.5 例 1」树的统计（ZJOI2008）
题意：树上单点修改权值，查询任意两点路径上节点的权值和与权值最大值。
思路：树链剖分(HLD)把树上路径拆成 O(log n) 段，每段对应一段 dfn 连续区间。
用线段树维护区间和与区间最大值，支持单点修改与区间查询。
复杂度：时间 O((n+q)log^2 n)，空间 O(n)。
易错点：CHANGE 是单点改权值不是区间改；权值可负，QMAX 初值要用 -INF；
HLD 跳链时让深度大的链头先往上跳，保证复杂度。
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 30005;
const int INF = 0x3f3f3f3f;
int n;
vector<int> g[MAXN];
int w[MAXN];
int fa[MAXN], dep[MAXN], sz[MAXN], son[MAXN], top[MAXN], dfn[MAXN], rk[MAXN], tim;
void dfs1(int u, int p){
    fa[u] = p;
    dep[u] = dep[p] + 1;
    sz[u] = 1;
    son[u] = 0;
    for(int v : g[u]){
        if(v == p) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if(sz[v] > sz[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int tp){
    top[u] = tp;
    dfn[u] = ++tim;
    rk[tim] = u;
    if(son[u]) dfs2(son[u], tp);
    for(int v : g[u]){
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}
long long tree_sum[4 * MAXN];
int tree_max[4 * MAXN];
void pushup(int o){
    tree_sum[o] = tree_sum[o * 2] + tree_sum[o * 2 + 1];
    tree_max[o] = max(tree_max[o * 2], tree_max[o * 2 + 1]);
}
void build(int o, int l, int r){
    if(l == r){
        tree_sum[o] = w[rk[l]];
        tree_max[o] = w[rk[l]];
        return;
    }
    int mid = (l + r) / 2;
    build(o * 2, l, mid);
    build(o * 2 + 1, mid + 1, r);
    pushup(o);
}
void update(int o, int l, int r, int p, int v){
    if(l == r){
        tree_sum[o] = v;
        tree_max[o] = v;
        return;
    }
    int mid = (l + r) / 2;
    if(p <= mid) update(o * 2, l, mid, p, v);
    else update(o * 2 + 1, mid + 1, r, p, v);
    pushup(o);
}
long long qsum;
int qmax;
void query(int o, int l, int r, int ql, int qr){
    if(ql <= l && r <= qr){
        qsum += tree_sum[o];
        qmax = max(qmax, tree_max[o]);
        return;
    }
    int mid = (l + r) / 2;
    if(ql <= mid) query(o * 2, l, mid, ql, qr);
    if(qr > mid) query(o * 2 + 1, mid + 1, r, ql, qr);
}
long long path_sum(int u, int v){
    long long res = 0;
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        qsum = 0;
        query(1, 1, n, dfn[top[u]], dfn[u]);
        res += qsum;
        u = fa[top[u]];
    }
    if(dep[u] > dep[v]) swap(u, v);
    qsum = 0;
    query(1, 1, n, dfn[u], dfn[v]);
    res += qsum;
    return res;
}
int path_max(int u, int v){
    int res = -INF;
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        qmax = -INF;
        query(1, 1, n, dfn[top[u]], dfn[u]);
        res = max(res, qmax);
        u = fa[top[u]];
    }
    if(dep[u] > dep[v]) swap(u, v);
    qmax = -INF;
    query(1, 1, n, dfn[u], dfn[v]);
    res = max(res, qmax);
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i = 1; i <= n; i++) cin >> w[i];
    dfs1(1, 0);
    dfs2(1, 1);
    build(1, 1, n);
    int q;
    cin >> q;
    while(q--){
        string op;
        cin >> op;
        if(op == "CHANGE"){
            int u, t;
            cin >> u >> t;
            update(1, 1, n, dfn[u], t);
        } else if(op == "QMAX"){
            int u, v;
            cin >> u >> v;
            cout << path_max(u, v) << "\n";
        }else{
            int u, v;
            cin >> u >> v;
            cout << path_sum(u, v) << "\n";
        }
    }
    return 0;
}
树的统计

正文

一本通·提高篇的其它内容
