Description#

给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v,k)，你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案，初始为0，即第一个询问的u是明文。

Input#

第一行两个整数N,M。 第二行有N个整数，其中第i个整数表示点i的权值。 后面N-1行每行两个整数(x,y)，表示点x到点y有一条边。 最后M行每行两个整数(u,v,k)，表示一组询问。

Output#

M行，表示每个询问的答案。最后一个询问不输出换行符

Sample Input#

8 5
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1
0 5 2
10 5 3
11 5 4
110 8 2

Sample Output#

2
8
9
105
7

题解#

简单来说可以每个节点复制他父亲的节点在新版本中插入自己
然后两个点之间的k小值就是a-lca + b-fa[lca];

#include <cstdio>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;
struct Seg_Node *null;
struct Seg_Node
{
    Seg_Node *ch[2];
    int cnt;
    //#define cnt(_) ((_) ? (_)->cnt : 0)
    Seg_Node(Seg_Node *l, Seg_Node *r)
    {
        ch[0] = l, ch[1] = r;
        cnt = ch[0]->cnt + ch[1]->cnt;
    }
    Seg_Node(Seg_Node *l, Seg_Node *r, int _cnt)
    {
        ch[0] = l, ch[1] = r;
        cnt = _cnt;
    }
    Seg_Node *insert(int l, int r, int x)
    {
        if (l == r)
            return new Seg_Node(null, null, cnt + 1);
        else
        {
            int m = l + (r - l) / 2;
            if (x <= m)
                return new Seg_Node(ch[0]->insert(l, m, x), ch[1]);
            else
                return new Seg_Node(ch[0], ch[1]->insert(m + 1, r, x));
        }
    }
};
struct Node
{
    vector<Node *> ch;
    Node *fa;
    int dep, w;
    bool vis;
    Seg_Node *Seg;
} v[100005];
 
void addedge(int a, int b)
{
    v[a].ch.push_back(&v[b]);
    v[b].ch.push_back(&v[a]);
}
void init()
{
    null = new Seg_Node(NULL, NULL, 0);
    null->ch[0] = null->ch[1] = null;
}
int n, f[100005][20], logn;
void build()
{
    v[0].vis = 1;
    v[0].Seg = null;
    queue<Node *> Q;
    Q.push(&v[1]);
    v[1].vis = 1;
    v[1].dep = 1;
    v[1].fa = &v[0];
    while (!Q.empty())
    {
        Node *e = Q.front();
        Q.pop();
        e->Seg = e->fa->Seg->insert(0, INT_MAX, e->w);
        for (Node **p = &e->ch.front(), *u = *p; p <= &e->ch.back(); u = *++p)
        {
            if (!u->vis)
            {
                u->vis = 1;
                u->dep = e->dep + 1;
                u->fa = e;
                Q.push(u);
            }
        }
    }
    while ((1 << (logn + 1)) <= n)
        logn++;
    f[1][0] = 1;
    for (int i = 2; i <= n; i++)
        f[i][0] = v[i].fa - v;
    for (int j = 1; j <= logn; j++)
    {
        for (int i = 1; i <= n; i++)
        {
            f[i][j] = f[f[i][j - 1]][j - 1];
        }
    }
}
int lca(int s, int e)
{
    if (v[s].dep < v[e].dep)
        swap(s, e);
    if (v[s].dep > v[e].dep)
    {
        for (int i = logn; i >= 0; i--)
        {
            if (v[f[s][i]].dep >= v[e].dep)
                s = f[s][i];
        }
    }
    if (s != e)
    {
        for (int i = logn; i >= 0; i--)
        {
            if (f[s][i] != f[e][i])
            {
                s = f[s][i];
                e = f[e][i];
            }
        }
        return f[s][0];
    }
    return s;
}
int Query(int s, int e, int k)
{
    int p = lca(s, e);
    Seg_Node *Su = v[s].Seg, *Sv = v[e].Seg, *Sp = v[p].Seg, *Sf = v[p].fa->Seg;
    int l = 0, r = INT_MAX;
    while (l < r)
    {
        int m = l + (r - l) / 2;
        int S = Su->ch[0]->cnt + Sv->ch[0]->cnt - Sp->ch[0]->cnt - Sf->ch[0]->cnt;
        if (k > S)
        {
            k -= S;
            l = m + 1;
            Su = Su->ch[1];
            Sv = Sv->ch[1];
            Sp = Sp->ch[1];
            Sf = Sf->ch[1];
        }
        else
        {
            r = m;
            Su = Su->ch[0];
            Sv = Sv->ch[0];
            Sp = Sp->ch[0];
            Sf = Sf->ch[0];
        }
    }
    return l;
}
int main()
{
    int m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &v[i].w);
    for (int i = 1; i <= n - 1; i++)
    {
        int s, e;
        scanf("%d%d", &s, &e);
        addedge(s, e);
    }
    init();
    build();
    int ans = 0;
    while (m--)
    {
        int s, e, k;
        scanf("%d%d%d", &s, &e, &k);
        s ^= ans;
        printf(m ? "%d\n" : "%d", ans = Query(s, e, k));
    }
}