P5478 [BJOI2015] 骑士的旅行 - 重链剖分

首先分析一下题目，对于这棵树，操作如下：

1. 查询从 X 到 Y 的路径上的前 k 大的值。
2. 把 $P_i$ 上的武力值减去一个 $F_i$ 并在 Y 上的武力值加上一个 $F_i$，再把 $P_i$ 改成 Y。
3. 将 $P_i$ 上的武力值减去一个 $F_i$ 再加上一个 Y，并把 $F_i$ 改成 Y。

由第一个我们可以想到，先用树剖，再用线段树处理。每个节点上存储该范围下的前 k 大，每个地方的武力值就用 multiset 存下来就可以了。因为 $k \le 20$，所以每个叶子节点暴力更新就可以了。PushUp 就用归并排序的方式合并两个子节点的前 k 大，最后用常规的树剖操作查询就结束了。

#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const int N = 40000 + 5;
int n, m, Q, K;
int F[N], P[N];
vector<int> V[N];
multiset <int, greater<int> > S[N];
int fa[N], dep[N], siz[N], son[N];
int top[N], id[N], cnt;
void dfs1(int sx, int ffa) {
    fa[sx] = ffa;
    dep[sx] = dep[ffa] + 1;
    siz[sx] = 1;
    int maxn = -1;
    for (auto to : V[sx]) {
        if (to == ffa) continue;
        dfs1 (to, sx);
        siz[sx] += siz[to];
        if (siz[to] > maxn) {
            maxn = siz[to];
            son[sx] = to;
        }
    }
    return ;
}
void dfs2(int sx, int topf) {
    top[sx] = topf;
    id[sx] = ++ cnt;
    if (son[sx]) dfs2 (son[sx], topf);
    for (auto to : V[sx]) {
        if (to == fa[sx] || to == son[sx]) continue;
        dfs2 (to, to);
    }
    return ;
}
struct sgt {
    struct node {
        int res[25], len;
    }sum[N << 2];
    node merge(node A, node B) {
        node C;
        C.len = 0;
        int i = 1, j = 1;
        while (i <= A.len && j <= B.len && C.len < K) {
            if (A.res[i] > B.res[j])
                C.res[++ C.len] = A.res[i ++];
            else C.res[++ C.len] = B.res[j ++];
        }
        while (i <= A.len && C.len < K) C.res[++ C.len] = A.res[i ++];
        while (j <= B.len && C.len < K) C.res[++ C.len] = B.res[j ++];
        return C;
    }
    void PushUp (int u) {
        sum[u] = merge(sum[u << 1], sum[u << 1 | 1]);
        return ;
    }
    void build (int u, int l, int r) {
        if (l == r) {
            sum[u].len = 0;
            for (auto i : S[l]) {
                sum[u].res[++ sum[u].len] = i;
                if (sum[u].len == K)
                    break;
            }
            return ;
        }
        int mid = l + r >> 1;
        build (u << 1, l, mid);
        build (u << 1 | 1, mid + 1, r);
        PushUp (u);
    }
    void modify(int u, int l, int r, int pos, int add, int red) {
        if (l == r) {
            if (add != -1) S[pos].emplace (add);
            if (red != -1) S[pos].erase (S[pos].find(red));
            sum[u].len = 0;
            for (auto i : S[l]) {
                sum[u].res[++ sum[u].len] = i;
                if (sum[u].len == K)
                    break;
            }
            return ;
        }
        int mid = l + r >> 1;
        if (pos <= mid)
            modify (u << 1, l, mid, pos, add, red);
        if (mid < pos)
            modify (u << 1 | 1, mid + 1, r, pos, add, red);
        PushUp (u);
        return ;
    }
    node query(int u, int l, int r, int L, int R) {
        if (L <= l && r <= R) return sum[u];
        int mid = l + r >> 1;
        if (R <= mid)
            return query (u << 1, l, mid, L, R);
        if (L > mid)
            return query (u << 1 | 1, mid + 1, r, L, R);
        return merge (query (u << 1, l, mid, L, R), query (u << 1 | 1, mid + 1, r, L, R));
    }
    node get(int x, int y) {
        node ans;
        ans.len = 0;
        while (top[x] != top[y]) {
            if (dep[top[x]] > dep[top[y]])
                swap (x, y);
            ans = merge (ans, query (1, 1, n, id[top[y]], id[y]));
            y = fa[top[y]];
        }
        if (dep[x] > dep[y]) swap (x, y);
        ans = merge (ans, query (1, 1, n, id[x], id[y]));
        return ans;
    }
}tre;
int main() {
    scanf ("%d", &n);
    for (int i = 1;i < n; ++ i) {
        int u, v;
        scanf ("%d%d", &u, &v);
        V[u].push_back(v);
        V[v].push_back(u);
    }
    scanf ("%d", &m);
    for (int i = 1;i <= m; ++ i)
        scanf ("%d%d", F + i, P + i);
    dfs1 (1, 1);
    dfs2 (1, 1);
    for (int i = 1;i <= m; ++ i) 
        S[id[P[i]]].emplace (F[i]);
    scanf ("%d%d", &Q, &K);
    tre.build(1, 1, n);
    while (Q--) {
        int opt, X, Y;
        scanf ("%d%d%d", &opt, &X, &Y);
        if (opt == 1) {
            sgt :: node ans;
            ans = tre.get (X, Y);
            for (int i = 1;i <= ans.len; ++ i)
                printf ("%d ", ans.res[i]);
            if (ans.len == 0) printf ("-1");
            puts("");
        }
        if (opt == 2) {
            tre.modify (1, 1, n, id[P[X]], -1, F[X]);
            P[X] = Y;
            tre.modify (1, 1, n, id[P[X]], F[X], -1);
        }
        if (opt == 3) {
            tre.modify (1, 1, n, id[P[X]], Y, F[X]);
            F[X] = Y;
        }
    }
    return 0;
}