题意：有一棵N个点的树，每个点有对应的权值，现在有这样的操作，“0 a b”将a点的权值改成为b，“k a b”询问a到b的链上第k大的权值是几。
我们可以用dfs序的树上差分的方式来解决这个问题，可以发现，求u到v的信息，其实就是求u到lca和v到lca的合并，所以我们得想办法把这条链上的第k大给处理出来，这时候可以使用主席树来进行操作，我们不妨给点u赋值的时候，赋值给dfn[u]~dfn[u]+siz[u]-1，是这棵子树上的所有的点都被给予了这个值，不妨在dfn[u]位置“+1”，dfn[u]+siz[u]的位置上“-1”，用dfs序的方式将他们放到了一条链上去进行差分。
但是现在有了修改的操作，我们改变一个值的时候，实际上会对他的所有的子树造成影响，所以我们改成给原来的每个点都是一棵主席树，我们将原来的dfs序成的序列拿出来，看成一维轴的形式，然后，就是对这个一维的轴进行操作了。
那么，我们可以利用树状数组，对这个前缀差分来进行操作，不妨在dfn[u]的点处先减去原来的点权的贡献，再换上新的点权，然后同理不要忘记dfn[u]+siz[u]这个位置的操作。
#include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <limits> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #include <bitset> #include <unordered_map> #include <unordered_set> #define lowbit(x) ( x&(-x) ) #define pi 3.141592653589793 #define e 2.718281828459045 #define eps 1e-8 #define INF 0x3f3f3f3f #define HalF (l + r)>>1 #define lsn rt<<1 #define rsn rt<<1|1 #define Lson lsn, l, mid #define Rson rsn, mid+1, r #define QL Lson, ql, qr #define QR Rson, ql, qr #define myself rt, l, r using namespace std; typedef unsigned long long ull; typedef unsigned int uit; typedef long long ll; const int maxN = 8e4 + 7; int N, Q, head[maxN], cnt, a[maxN], Lsan[maxN << 1], _UP; vector<int> bin; struct Eddge { int nex, to; Eddge(int a=-1, int b=0):nex(a), to(b) {} } edge[maxN << 1]; inline void addEddge(int u, int v) { edge[cnt] = Eddge(head[u], v); head[u] = cnt++; } inline void _add(int u, int v) { addEddge(u, v); addEddge(v, u); } struct Question { int k, a, b; void In() { scanf("%d%d%d", &k, &a, &b); } } ques[maxN]; int siz[maxN], fa[maxN], deep[maxN], Wson[maxN]; void dfs_1(int u, int father) { siz[u] = 1; fa[u] = father; deep[u] = deep[father] + 1; for(int i=head[u], v; ~i; i=edge[i].nex) { v = edge[i].to; if(v == father) continue; dfs_1(v, u); if(siz[v] > siz[Wson[u]]) Wson[u] = v; } } int top[maxN], dfn[maxN], rid[maxN], tim, End_tim[maxN]; void dfs_2(int u, int topy) { top[u] = topy; dfn[u] = ++tim; rid[tim] = u; if(Wson[u]) dfs_2(Wson[u], topy); for(int i=head[u], v; ~i; i=edge[i].nex) { v = edge[i].to; if(v == fa[u] || v == Wson[u]) continue; dfs_2(v, v); } End_tim[u] = tim; } int _LCA(int u, int v) { while(top[u] ^ top[v]) { if(deep[top[u]] < deep[top[v]]) swap(u, v); u = fa[top[u]]; } if(deep[u] > deep[v]) swap(u, v); return u; } const int max_T = maxN * 400; int t[max_T], lc[max_T], rc[max_T], tot, root[maxN]; void Insert(int &now, int old, int l, int r, int pos, int val) { if(!now) now = ++tot; t[now] = t[old] + val; lc[now] = lc[old]; rc[now] = rc[old]; if(l == r) return; int mid = HalF; if(pos <= mid) Insert(lc[now], lc[old], l, mid, pos, val); else Insert(rc[now], rc[old], mid + 1, r, pos, val); } void Pre_update(int x, int pos, int val) { while(x <= N) { Insert(root[x], root[x], 1, _UP, pos, val); x += lowbit(x); } } int tmp_1[maxN], tmp_2[maxN], t1, t2; int query(int l, int r, int kth) { int mid, sum; while(l ^ r) { mid = HalF; sum = 0; for(int i=1; i<=t1; i++) sum += t[rc[tmp_1[i]]]; for(int i=1; i<=t2; i++) sum -= t[rc[tmp_2[i]]]; if(sum >= kth) { for(int i=1; i<=t1; i++) tmp_1[i] = rc[tmp_1[i]]; for(int i=1; i<=t2; i++) tmp_2[i] = rc[tmp_2[i]]; l = mid + 1; } else { for(int i=1; i<=t1; i++) tmp_1[i] = lc[tmp_1[i]]; for(int i=1; i<=t2; i++) tmp_2[i] = lc[tmp_2[i]]; r = mid; kth -= sum; } } return l; } int Pre_Query(int u, int v, int kth) { t1 = t2 = 0; for(int i=dfn[u]; i; i -= lowbit(i)) tmp_1[++t1] = root[i]; for(int i=dfn[v]; i; i -= lowbit(i)) tmp_1[++t1] = root[i]; int lca = _LCA(u, v); if(deep[u] + deep[v] - deep[lca] - deep[fa[lca]] < kth) return -1; for(int i=dfn[lca]; i; i -= lowbit(i)) tmp_2[++t2] = root[i]; for(int i=dfn[fa[lca]]; i; i -= lowbit(i)) tmp_2[++t2] = root[i]; return query(1, _UP, kth); } void dfs_3(int u, int ff) { Pre_update(dfn[u], a[u], 1); Pre_update(End_tim[u] + 1, a[u], -1); for(int i=head[u], v; ~i; i=edge[i].nex) { v = edge[i].to; if(v == ff) continue; dfs_3(v, u); } } inline void init() { cnt = 0; _UP = N; tim = 0; tot = 0; for(int i=1; i<=N; i++) head[i] = -1; } int main() { scanf("%d%d", &N, &Q); for(int i=1; i<=N; i++) { scanf("%d", &a[i]); Lsan[i] = a[i]; } init(); for(int i=1, u, v; i<N; i++) { scanf("%d%d", &u, &v); _add(u, v); } for(int i=1; i<=Q; i++) { ques[i].In(); if(!ques[i].k) Lsan[++_UP] = ques[i].b; } sort(Lsan + 1, Lsan + _UP + 1); _UP = (int)(unique(Lsan + 1, Lsan + _UP + 1) - Lsan - 1); for(int i=1; i<=N; i++) a[i] = (int)(lower_bound(Lsan + 1, Lsan + _UP + 1, a[i]) - Lsan); for(int i=1; i<=Q; i++) if(!ques[i].k) ques[i].b = (int)(lower_bound(Lsan + 1, Lsan + _UP + 1, ques[i].b) - Lsan); dfs_1(1, 0); dfs_2(1, 1); dfs_3(1, 0); int ans; for(int i=1; i<=Q; i++) { if(ques[i].k == 0) { Pre_update(dfn[ques[i].a], a[ques[i].a], -1); Pre_update(End_tim[ques[i].a] + 1, a[ques[i].a], 1); Pre_update(dfn[ques[i].a], ques[i].b, 1); Pre_update(End_tim[ques[i].a] + 1, ques[i].b, -1); a[ques[i].a] = ques[i].b; } else { ans = Pre_Query(ques[i].a, ques[i].b, ques[i].k); if(~ans) { printf("%d\n", Lsan[ans]); } else { printf("invalid request!\n"); } } } return 0; }
