刚学会主席树，胡乱找了一些主席树的题，结果差不多都是板，我还调了很久。
题目很人性不翻译了。
强制在线毁我终生，导致我WA0->RE0反正都是爆零。
主席树是满足前缀和性质的数据结构，这个在敲板子的时候都知道。对于这道题，我们可以设 $s_u$ 表示点 $u$ 到根节点的路径上的一颗线段树，维护这条路径上的各个大小所有数字出现的出现的次数（肯定要离散化的，不多说）。
那么求 $u,v$ 两点的第 $k$ 小，对应的线段树是：$s_u+s_v-s_{lca(u,v)}-s_{fa(lca(u,v))}$。
好像挺简单啊。
然而我调了一个下午+晚上。原因是惯性地把某个点减了一（就是求 $k$ 小的板子，打惯了）。
内心：你tmd怎么这么菜啊，一道板子调一天。
$Code:$
```cpp
include
include
include
include
const int N = 1e5 + 5;
std::vector
int A[N], Fa[N][18], Dep[N], Key[N], num[N], n, tot;
struct node {
int idx, v, rnk;
inline bool operator < (const node X) {return v < X.v;}
} B[N];
struct kachang {
inline bool operator () (const node X, const node Y) const {return X.idx < Y.idx;}
};
inline int LCA(int u, int v) {
if (Dep[u] < Dep[v]) u ^= v ^= u ^= v;
int S(ceil(log2(Dep[u] - Dep[v])));
for (int i(0); i <= S; ++ i) if (Dep[u] - Dep[v] & 1 << i) u = Fa[u][i];
if (u == v) return u;
for (int i(ceil(log2(Dep[u]))); ~i; — i)
if (Fa[u][i] != Fa[v][i]) u = Fa[u][i], v = Fa[v][i];
return Fa[u][0];
}
struct Chairman_tree {
int cnt[N << 5], ls[N << 5], rs[N << 5], root[N], x, tot;
inline void Update(int k, int _x, int pre) {
x = _x, update(root[k] = ++ tot, 1, n, root[pre]);
}
inline int Query(int u, int v, int k) {
int lca(LCA(u, v));
u = num[u], v = num[v];
if (u > v) u ^= v ^= u ^= v;
return query(root[u], root[v], root[num[lca]], root[num[Fa[lca][0]]], 1, n, k);
}
inline void build() {make_tree(root[0] = tot = 1, 1, n);}
void make_tree(int p, int l, int r) {
if (l == r) return;
int mid(l + r >> 1);
make_tree(ls[p] = ++ tot, l, mid), make_tree(rs[p] = ++ tot, mid + 1, r);
}
void update(int u, int l, int r, int root) {
if (l == r) {cnt[u] = cnt[root] + 1; return;}
int mid(l + r >> 1);
if (mid >= x) update(ls[u] = ++ tot, l, mid, ls[root]), rs[u] = rs[root];
else update(rs[u] = ++ tot, mid + 1, r, rs[root]), ls[u] = ls[root];
cnt[u] = cnt[ls[u]] + cnt[rs[u]];
}
int query(int u, int v, int lca, int falca, int l, int r, int d) {
if (l == r) return l;
int x(cnt[ls[u]] + cnt[ls[v]] - cnt[ls[lca]] - cnt[ls[falca]]), mid(l + r >> 1);
return d <= x ? query(ls[u], ls[v], ls[lca], ls[falca], l, mid, d) :
query(rs[u], rs[v], rs[lca], rs[falca], mid + 1, r, d - x);
}
} Tree;
void dfs(int u) {
Tree.Update(num[u] = ++ tot, B[u].rnk, num[Fa[u][0]]);
int S(ceil(log2(Dep[u] = Dep[Fa[u][0]] + 1)));
for (int i(1); i <= S; ++ i) Fa[u][i] = Fa[Fa[u][i - 1]][i - 1];
for (int i : sons[u]) if (i != Fa[u][0]) Fa[i][0] = u, dfs(i);
}
int main() {
int m, last(0);
scanf(“%d%d”, &n, &m);
Tree.build();
for (int i(1); i <= n; ++ i) scanf(“%d”, A + i), B[i].v = A[i], B[i].idx = i;
std::sort(B + 1, B + n + 1);
Key[B[1].rnk = 1] = B[1].v;
for (int i(2); i <= n; ++ i)
Key[B[i].rnk = (B[i - 1].v == B[i].v ? B[i - 1].rnk : B[i - 1].rnk + 1)] = B[i].v;
std::sort(B + 1, B + n + 1, kachang());
for (int i(1); i < n; ++ i) {
int u, v;
scanf(“%d%d”, &u, &v);
sons[u].push_back(v), sons[v].push_back(u);
}
dfs(1);
while (m —) {
int u, v, k;
scanf(“%d%d%d”, &u, &v, &k);
printf(“%d\n”, last = Key[Tree.Query(u ^ last, v, k)]);
}
}