[SPOJ375]QTREE - Query on a tree【树链剖分】

题目描述

给你一棵树，两种操作。
修改边权，查找边权的最大值。

分析

我们都知道，树链剖分能够维护点权。
而且每一条边只有一个，且唯一对应一个儿子节点，那么就把信息放到这个儿子节点上。
注意，lca的信息不能算到，也就是当查询到了\(top[u]=top[v]\)的时候，要从\(idx[u]+1\)到\(v\)的查询，因为\(idx[u]\)为lca。

代码

#include <bits/stdc++.h>
#define ms(a, b) memset(a, b, sizeof(a))
#define ll long long
#define ull unsigned long long 
#define ms(a, b) memset(a, b, sizeof(a))
#define inf 0x3f3f3f3f
#define db double 
#define Pi acos(-1)
#define eps 1e-8
#define N 200005
using namespace std;
template <typename T> void read(T &x) {
    x = 0; T fl = 1; char ch = 0;
    for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') fl = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    x *= fl;
}
template <typename T> void write(T x) {
    if (x < 0) x = -x, putchar('-');
    if (x > 9) write(x / 10); putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) { write(x); puts(""); }
struct edge {
    int to, nt, w;
}E[N << 1];
int H[N], top[N], dep[N], son[N], idx[N], fa[N], sz[N], val[N], a[N], U[N], V[N];
int cnt, tot = 0, n;
void add_edge(int u, int v, int w) {
    E[++ cnt] = (edge){v, H[u], w}; 
    H[u] = cnt;
}
struct Segment_Tree {
    #define lc (nod << 1)
    #define rc (nod << 1 | 1)
    struct node {
        int mx, l, r;
    }tr[N << 2];
    void pushup(int nod) { tr[nod].mx = max(tr[lc].mx, tr[rc].mx); }
    void build(int nod, int l, int r, int *a) {
        tr[nod].l = l, tr[nod].r = r; tr[nod].mx = -inf;
        if (l == r) { tr[nod].mx = a[l]; return; }
        int mid = (l + r) >> 1;
        build(lc, l, mid, a); build(rc, mid + 1, r, a);
        pushup(nod);
    }
    void update(int nod, int k, int val) {
        int l = tr[nod].l, r = tr[nod].r;
        if (l == r) { tr[nod].mx = val; return; }
        int mid = (l + r) >> 1;
        if (k <= mid) update(lc, k, val); else update(rc, k, val);
        pushup(nod);
    }
    int query(int nod, int ql, int qr) {
        int l = tr[nod].l, r = tr[nod].r;
        if (ql <= l && r <= qr) return tr[nod].mx; 
        int mid = (l + r) >> 1, res = -inf;
        if (ql <= mid) res = max(res, query(lc, ql, qr));
        if (qr > mid) res = max(res, query(rc, ql, qr));
        return res;
    }
}sgt;
void dfs1(int u, int ft, int dp) {
    dep[u] = dp; fa[u] = ft; sz[u] = 1;
    int maxson = -1;
    for (int e = H[u]; e; e = E[e].nt) {
        int v = E[e].to; if (v == fa[u]) continue;
        dfs1(v, u, dp + 1);
        a[v] = E[e].w;  sz[u] += sz[v];
        if (sz[v] > maxson) maxson = sz[v], son[u] = v;
    }
}
void dfs2(int u, int tp) {
    top[u] = tp; idx[u] = ++ tot; val[tot] = a[u];
    if (!son[u]) return; dfs2(son[u], tp);
    for (int e = H[u]; e; e = E[e].nt) { 
        int v = E[e].to; 
        if (v == fa[u] || v == son[u]) continue; 
        dfs2(v, v); 
    }
}
char opt[10];
int query_chain(int u, int v) {
    int res = -inf;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        res = max(res, sgt.query(1, idx[top[u]], idx[u]));
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    res = max(res, sgt.query(1, idx[u] + 1, idx[v]));
    return res;
}
int main() {
    read(n);
    for (int i = 1; i < n; i ++) {
        int u, v, w; read(u); read(v); read(w);
        add_edge(u, v, w); add_edge(v, u, w);
        U[i] = u; V[i] = v;
    }
    dfs1(1, 0, 1); dfs2(1, 1);
    sgt.build(1, 1, n, val);
    while (scanf("%s", opt) != EOF) {
        if (opt[0] == 'D') return 0;
        int x, y; read(x); read(y);
        if (opt[0] == 'Q') writeln((x != y)? query_chain(x, y): 0);
        else {
            int u = U[x], v = V[x]; 
            if (fa[v] == u) swap(u, v); 
            sgt.update(1, idx[u], y);
        }
    }
    return 0;
}