给一颗n个节点的树，节点有权值，求以u，v为端点的条上权值第k小。
\(n,m<1e5\)询问在线。
显然要用主席树维护。
但是，很难将链转化为序列。
所以要一种巧妙的做法。
每个节点的主席树由它的父亲继承下来。
然后，查询链的时候，只需要减去u，v的LCA和LCA的父亲的贡献即可。
#include <bits/stdc++.h> using namespace std; #define DEBUG(...) fprintf(stderr, __VA_ARGS__) #define mp make_pair #define fst first #define snd second template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } inline int read(){ int res = 0, fl = 1; char r = getchar(); for (; !isdigit(r); r = getchar()) if(r == '-') fl = -1; for (; isdigit(r); r = getchar()) res = (res << 3) + (res << 1) + r - 48; return res * fl; } typedef long long LL; typedef pair<int, int> pii; const int Maxn = 1e5 + 10; struct SGT{ int ls,rs,sum; }tre[Maxn << 6]; int val[Maxn], fa[Maxn][30], cnt, dep[Maxn]; int num, root[Maxn << 6], B[Maxn]; vector <int> g[Maxn]; int LCA(int u,int v){ if(dep[u] < dep[v]) swap(u, v); for (int i = 18; i >= 0 ; --i) if(dep[fa[u][i]] >= dep[v]) u = fa[u][i]; if(u == v) return u; for (int i = 18; i >= 0 ; --i) if(fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i]; return fa[u][0]; } void build(int &rt,int grt,int l,int r,int pos){ tre[rt = ++cnt] = tre[grt]; tre[rt].sum++; if(l == r) return; int mid = l + r >> 1; if(pos <= mid) build(tre[rt].ls, tre[grt].ls, l, mid, pos); else build(tre[rt].rs, tre[grt].rs, mid + 1, r, pos); } int Query(int a,int b,int c,int d,int l,int r,int k){ if(l == r) return B[l]; int mid = l + r >> 1, t = tre[tre[a].ls].sum + tre[tre[b].ls].sum - tre[tre[c].ls].sum - tre[tre[d].ls].sum; if(k <= t) return Query(tre[a].ls, tre[b].ls, tre[c].ls, tre[d].ls, l, mid, k); else return Query(tre[a].rs, tre[b].rs, tre[c].rs, tre[d].rs, mid + 1, r, k - t); } void dfs(int now, int pa){ dep[now] = dep[pa] + 1; fa[now][0] = pa; for (int i = 1; i <= 18; ++i) fa[now][i] = fa[fa[now][i - 1]][i - 1]; build(root[now],root[pa], 1, num, val[now]); for (int i = g[now].size() - 1; i >= 0; --i){ int nxt = g[now][i]; if(nxt == pa) continue; dfs(nxt, now); } } int main() { #ifndef ONLINE_JUDGE freopen("a.in", "r", stdin); freopen("a.out", "w", stdout); #endif int n = read(), m = read(); for (int i = 1; i <= n; ++i) B[i] = val[i] = read(); sort(B + 1, B + 1 + n); num = unique(B + 1, B + 1 + n) - B - 1; for (int i = 1; i <= n; ++i) val[i] = lower_bound(B + 1, B + num + 1, val[i]) - B; for (int i = 1; i < n; ++i) { int x = read(), y = read(); g[x].push_back(y); g[y].push_back(x); } dfs(1,0); int ans = 0; while(m--){ int u = read() ^ ans, v = read(), k = read(); int lca = LCA(u,v),flca = fa[lca][0]; ans = Query(root[u],root[v],root[lca],root[flca],1,num,k); printf("%d\n",ans); } return 0; }转载于:https://www.cnblogs.com/LZYcaiji/p/10397850.html
相关资源：JAVA上百实例源码以及开源项目