题目传送门(BZOJ)
>原文链接<

题解 :

带修主席树,考虑树状数组套主席树

考虑不带修改怎么做 :

维护一棵主席树, 树上每个点的信息从父节点继承而来

这样, 在查询路径(a, b)的信息时, 查询Tree[a]+Tree[b]-Tree[LCA(a, b)]-Tree[fa[LCA(a, b)]]就行了

这是一个常见的套路, 就是简单的前缀和思想, 因为我们在这里用主席树维护的本来就是一个前缀信息

由于有了修改, 我们还要加上树状数组

考虑一个点权值改变,只会对它子树中所有点的信息产生影响,

dfn[p]odn[p],

前者是DFS序上p的标号,后者是退出p时, 当前标号记录到哪,也就是子树中dfn最大的节点的dfn

考虑一次修改 : 把p的权值从x改到y

相当于在dfn[p]\to n这段区间中减去一次权值x, 再加上一次权值y

再把oud[p]\to n这段区间加上一次权值x , 再减去一次权值y ,

因为刚刚的修改本来和这些节点无关,他们是多加/多减的

区间对主席树的修改, 就用树状数组维护即可.

代码实现还是略有复杂的, 但是思路清晰的话, 没有什么特别难以理解的地方

要把适合于什么时候做的操作放到该在的时候

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)#define rep(i, a, b) for(int i = a; i <= b; i ++ )char buf[100000],*p1,*p2;inline int rd() { int x = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) x = (x<<1) + (x<<3) + (ch^48), ch = nc(); return x;}const int N = 81000;const int INF = 1e9;struct Edge { int to; Edge *next;}*h[N],e[N<<1];int val[N], siz[N], son[N], dep[N], fa[N], top[N];int dfn[N], odn[N], qrx[N], qry[N], qrz[N], qrw[N];int t[N<<8], ls[N<<8], rs[N<<8], root[N], n, m;inline void Add_Edge(int u, int v) { static int _; Edge *tmp = &e[++_]; tmp->to = v; tmp->next = h[u]; h[u] = tmp;}void insert(int l, int r, int &p, int x, int c) { static int _; if(!p) p = ++_; t[p] += c; if(l == r) return ; int mi = (l+r) >> 1; if(x <= mi) insert(l, mi, ls[p], x, c); else insert(mi+1, r, rs[p], x, c);}void dfs(int p) { dep[p] = dep[fa[p]]+1; siz[p] = 1; dfn[p] = ++*dfn; for(int i = dfn[p]; i <= n; i += i&-i ) insert(0, INF, root[i], val[p], 1); rev(i, p) { if(i->to != fa[p]) { fa[i->to] = p; dfs(i->to); if(siz[i->to] > siz[son[p]]) son[p] = i->to; siz[p] += siz[i->to]; } } for(int i = *dfn+1; i <= n; i += i&-i ) insert(0, INF, root[i], val[p], -1); odn[p] = *dfn+1;}void dfs(int p, int t) { top[p] = t; if(son[p]) dfs(son[p], t); rev(i, p) if(i->to != son[p] && i->to != fa[p]) dfs(i->to, i->to);}int lca(int x, int y) { while(top[x] != top[y]) { if(dep[top[x]] < dep[top[y]]) swap(x, y); x = fa[top[x]]; } return dep[x] < dep[y] ? x : y;}int inq(int l, int r, int k) { if(l == r) return l; int mi = (l+r) >> 1, sizl = 0; for(int i = 1; i <= *qrx; i ++ ) sizl += t[ls[qrx[i]]]; for(int i = 1; i <= *qry; i ++ ) sizl += t[ls[qry[i]]]; for(int i = 1; i <= *qrz; i ++ ) sizl -= t[ls[qrz[i]]]; for(int i = 1; i <= *qrw; i ++ ) sizl -= t[ls[qrw[i]]]; if(k <= sizl) { for(int i = 1; i <= *qrx; i ++ ) qrx[i] = ls[qrx[i]]; for(int i = 1; i <= *qry; i ++ ) qry[i] = ls[qry[i]]; for(int i = 1; i <= *qrz; i ++ ) qrz[i] = ls[qrz[i]]; for(int i = 1; i <= *qrw; i ++ ) qrw[i] = ls[qrw[i]]; return inq(l, mi, k); } else { for(int i = 1; i <= *qrx; i ++ ) qrx[i] = rs[qrx[i]]; for(int i = 1; i <= *qry; i ++ ) qry[i] = rs[qry[i]]; for(int i = 1; i <= *qrz; i ++ ) qrz[i] = rs[qrz[i]]; for(int i = 1; i <= *qrw; i ++ ) qrw[i] = rs[qrw[i]]; return inq(mi+1, r, k-sizl); }}int main() { n = rd(), m = rd(); for(int i = 1; i <= n; i ++ ) val[i] = rd(); for(int i = 2; i <= n; i ++ ) { int u = rd(), v = rd(); Add_Edge(u, v), Add_Edge(v, u); } dfs(1), dfs(1, 1); while(m -- ) { int k = rd(), x = rd(), y = rd(); if(!k) { for(int i = dfn[x]; i <= n ; i += i&-i ) insert(0, INF, root[i], val[x], -1); for(int i = odn[x]; i <= n ; i += i&-i ) insert(0, INF, root[i], val[x], 1); val[x]=y; for(int i = dfn[x]; i <= n ; i += i&-i ) insert(0, INF, root[i], val[x], 1); for(int i = odn[x]; i <= n ; i += i&-i ) insert(0, INF, root[i], val[x], -1); } else { *qrx = *qry = *qrz = *qrw = 0; int l = lca(x, y), f = fa[l]; int len = dep[x]+dep[y]-dep[l]-dep[f]; if(len < k) puts("invalid request!"); else { k = len-k+1; for(int i = dfn[x]; i; i -= i&-i) qrx[++*qrx] = root[i]; for(int i = dfn[y]; i; i -= i&-i) qry[++*qry] = root[i]; for(int i = dfn[l]; i; i -= i&-i) qrz[++*qrz] = root[i]; if(f) for(int i = dfn[f]; i; i -= i&-i) qrw[++*qrw] = root[i]; printf("%d\n", inq(0, INF, k)); } } }}