树剖 + 可持久化线段树 + 二分

#include <bits/stdc++.h>
#define ll long long
using namespace std;

#define il inline
#define rd read()
#define int long long

const int L = 2e5 + 10, mn = 2e5 + 10, inf = 1e9  +10;
int hs[L], sz[L], fa[L], top[L], wt[L], id[L], dep[L], cnt = 0; // 新编号
int head[L], nxt[L], edge[L], now = 0, a[L], b[L];
int root[L], n, m, num = 0, len;

struct NODE
{
    int ls, rs, sum;
}t[L << 5];

il int read()
{
    int res = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9')
    {
        if (c == '-') f = -1; 
        c = getchar();
    }
    while(c >= '0' && c <= '9')
    {
        res = res * 10 + c - 48; c = getchar();
    }
    return res * f;
}

il void addEdge(int u, int v)
{
    edge[++ now] = v;
    nxt[now] = head[u];
    head[u] = now;
}


il void dfs1(int st, int ff)
{
    fa[st] = ff, sz[st] = 1, dep[st] = dep[ff] + 1;
    root[st] = root[ff];
    int maxx = 0;
    for(int i = head[st]; i; i = nxt[i])
    {
        int j = edge[i];
        if(j == ff) continue;
        dfs1(j, st);
        sz[st] += sz[j];
        if(sz[j] > maxx) maxx = sz[j], hs[st] = j;
    }
}

il void dfs2(int st, int topf)
{
    id[st] = ++ cnt;
    top[st] = topf, wt[cnt] = a[st];
    if(!hs[st]) return;
    dfs2(hs[st], topf);
    for(int i = head[st]; i; i = nxt[i])
    {
        int j = edge[i];
        if(j == fa[st] || j == hs[st]) continue;
        dfs2(j, j);
    }
}

il void build(int &rt, int l = 1, int r = len)
{
    rt = ++ num;
    if(l == r) return;
    int mid = (l + r) / 2;
    build(t[rt].ls, l, mid), build(t[rt].rs, mid + 1, r);
}

il void modify(int pos, int &rt, int l = 1, int r = len)
{
    t[++ num] = t[rt]; rt = num;
    t[rt].sum ++;
    if(l == r) return;
    int mid = (l + r) / 2;
    if(pos <= mid) modify(pos, t[rt].ls, l, mid);
    else modify(pos, t[rt].rs, mid + 1, r);
}

il int query(int u, int v, int ql, int qr, int l = 1, int r = len)
{
    if(ql <= l && r <= qr) return t[v].sum - t[u].sum;
    int ans = 0;
    int mid = (l + r) / 2;
    if(ql <= mid) ans += query(t[u].ls, t[v].ls, ql, qr, l, mid);
    if(mid + 1 <= qr) ans += query(t[u].rs, t[v].rs, ql, qr, mid + 1, r);
    return ans;
}

il int query1(int l, int r, int k) {return query(root[l - 1], root[r], 1, k);};

il int queryT(int x, int y, int k)
{
    int ans = 0;
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        ans += query1(id[top[x]], id[x], k);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y); // now: id.x < id.y
    ans += query1(id[x], id[y], k);
    return ans;
}

il void pre()
{
    for(int i = 1; i <= n; ++i) a[i] = rd, b[i] = a[i];
    sort(b + 1, b + 1 + n);
    len = unique(b + 1, b + 1 + n) - b - 1;
    for(int i = 1; i <= n; ++i)
    {
        a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;
    }
}

il 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;
}

il void debug(int rt, int l = 1, int r = len)
{
    printf("[%lld %lld]: %lld\n", l, r, t[rt].sum);
    if(l == r) return;
    int mid = (l + r) / 2;
    debug(t[rt].ls, l, mid), debug(t[rt].rs, mid + 1, r);
}

signed main(void)
{
    n = rd; m = rd;
    int u, v;
    pre();
    for(int i = 1; i <= n - 1; ++i)
    {
        u = rd; v = rd;
        addEdge(u, v), addEdge(v, u);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    build(root[0]);
    for(int i = 1; i <= n; ++i) 
    {
        // printf("test: %lld\n", wt[i]);
        root[i] = root[i - 1];
        modify(wt[i], root[i]);
    }
    int k, la = 0;
    for(int i = 1; i <= m; ++i)
    {
        u = rd; v = rd; k = rd;
        int ans;
        u ^= la;
        int l = 0, r = len;
        while(l + 1 != r)
        {
            int mid = (l + r) / 2;
            // cout << mid << " " << queryT()
            if(queryT(u, v, mid) < k) l = mid;
            else r = mid;
        }
        ans = b[l + 1];
        la = ans;
        printf("%lld\n", ans);
    }
    return 0;
}

看到有佬说 离散化记得要用 len 不是 n， 我也用了 len，还是wa qwq

调了一下午了qwq，有没有人能帮忙看看，感谢