LuoguP2633 - Count on a tree

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
inline int read() {
    int e= 0, f= 1;
    char ch= getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-') f= -1;
        ch= getchar();
    }
    while(ch >= '0' && ch <= '9') e= e * 10 + ch - '0', ch= getchar();
    return e * f;
}
// READ
int n, m, d, vi[100005], lv[100005], edptr= 1, head[100005], tmpx, tmpy, tmpz;
struct edge {
    int to, nexty;
} eds[400001];
// 其实可以 100005 * 2
void add(int a, int b) {
    eds[edptr].to= b, eds[edptr].nexty= head[a];
    head[a]= edptr++;
    return;
}
// edge
struct NODE {
    NODE *l, *r;
    int v, sum;
} * root[800005];
// 其实可以 100005
NODE *build(int l, int r) {
    NODE *nptr= new NODE();
    if(l != r) {
        int mid= (l + r) >> 1;
        nptr->l= build(l, mid), nptr->r= build(mid + 1, r);
    }
    return nptr;
}
NODE *update(int l, int r, int c, NODE *pre) {
    NODE *nptr= new NODE();
    nptr->l= pre->l, nptr->r= pre->r, nptr->sum= pre->sum + 1;
    if(l != r) {
        int mid= (l + r) >> 1;
        if(c <= mid)
            nptr->l= update(l, mid, c, pre->l);
        else
            nptr->r= update(mid + 1, r, c, pre->r);
    }
    return nptr;
}
int query(NODE *ml, NODE *mr, NODE *xl, NODE *xr, int l, int r, int k) {
    if(l == r) return l;
    int qsum= mr->l->sum + ml->l->sum - xl->l->sum - xr->l->sum;
    int mid= (l + r) >> 1;
    if(qsum >= k) return query(ml->l, mr->l, xl->l, xr->l, l, mid, k);
    return query(ml->r, mr->r, xl->r, xr->r, mid + 1, r, k - qsum);
}
// tree
int deep[100005], f[100005][21];
void dfs(int nown, int fa) {
    deep[nown]= deep[fa] + 1;
    f[nown][0]= fa;
    for(int i= 0; i < 20; i++) f[nown][i + 1]= f[f[nown][i]][i];
    // 从0开始...Ciyang写挂了,写成从1开始,然后交了好多遍也没改对
    for(int i= head[nown], to; i; i= eds[i].nexty) {
        to= eds[i].to;
        if(to == fa) continue;
        dfs(to, nown);
    }
    return;
}
void dfs2(int nown) {
    root[nown]= update(1, n, lv[nown], root[f[nown][0]]);
    for(int i= head[nown], to; i; i= eds[i].nexty) {
        to= eds[i].to;
        if(to == f[nown][0]) continue;
        dfs2(to);
    }
    return;
}
int lca(int x, int y) {
    if(deep[x] < deep[y]) swap(x, y);
    for(int i= 19; i > -1; i--) {
        if(deep[f[x][i]] >= deep[y]) x= f[x][i];
        if(x == y) return x;
    }
    for(int i= 19; i > -1; i--)
        if(f[x][i] != f[y][i]) x= f[x][i], y= f[y][i];
    return f[x][0];
}
// LCA
int lastans= 0, tmpc;
int main() {
    n= read(), m= read();
    for(int i= 1; i <= n; i++) vi[i]= read(), lv[i]= vi[i];
    for(int i= 1; i < n; i++) {
        tmpx= read(), tmpy= read();
        add(tmpx, tmpy), add(tmpy, tmpx);
    }
    root[0]= build(1, n);
    sort(vi + 1, vi + n + 1);
    d= unique(vi + 1, vi + n + 1) - vi - 1;
    for(int i= 1; i <= n; i++) lv[i]= lower_bound(vi + 1, vi + d + 1, lv[i]) - vi;
    dfs(1, 0);
    dfs2(1);
    while(m--) {
        tmpx= read(), tmpy= read(), tmpz= read();
        tmpx^= lastans;
        tmpc= lca(tmpx, tmpy);
        lastans= vi[query(root[tmpx], root[tmpy], root[tmpc], root[f[tmpc][0]], 1, n, tmpz)];
        printf("%d\n", lastans);
    }
    return 0;
}
// main