题目链接：传送门

Description

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

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

Solution

主席树裸题，今天刚学的主席树。开始一直RE，后来把根的深度设为1就A掉了。。。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 100000 + 100;
int N, M;
int Root[Maxn], fa[Maxn], lastans, Cnt;
int Begin[Maxn * 2], To[Maxn * 2], Next[Maxn * 2], e;
int dep[Maxn], anc[Maxn][30], Rank[Maxn];

int A[Maxn], Re[Maxn], B[Maxn];

struct tree
{
    int lson, rson, val;
}Tree[Maxn * 64];

inline void add_edge (int x, int y)
{
    To[++e] = y;
    Next[e] = Begin[x];
    Begin[x] = e;
}

inline void build (int &root, int l, int r)
{
    root = ++ Cnt;
    if (l == r) return ;
    int mid = (l + r) >> 1;
    build(Tree[root].lson, l, mid);
    build(Tree[root].rson, mid + 1, r);
}

inline void Insert (int pre, int &now, int l, int r, int x)
{
    now = ++ Cnt;
    Tree[now].lson = Tree[pre].lson;
    Tree[now].rson = Tree[pre].rson;
    Tree[now].val = Tree[pre].val + 1;
    if (l == r) return ;
    int mid = (l + r) >> 1;
    if (x <= mid) Insert(Tree[pre].lson, Tree[now].lson, l, mid, x);
    else Insert(Tree[pre].rson, Tree[now].rson, mid + 1, r, x);
}

inline void dfs (int x)
{
    Insert(Root[fa[x]], Root[x], 1, N, A[x]);
    for (int i = 1; i <= 20; ++i)
        anc[x][i] = anc[anc[x][i - 1]][i - 1];
    for (int i = Begin[x]; i; i = Next[i])
    {
        int y = To[i];
        if (fa[x] == y) continue;
        dep[y] = dep[x] + 1;
        fa[y] = x;
        anc[y][0] = x;
        dfs(y);
    }
}

inline int lca (int x, int y)
{
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 20; i >= 0; --i)
        if (dep[anc[x][i]] >= dep[y])
            x = anc[x][i];
    if (x == y) return x;
    for (int i = 20; i >= 0; --i)
        if (anc[x][i] != anc[y][i])
            x = anc[x][i], y = anc[y][i];
    return fa[x];
}

inline int Query (int x, int y, int Lca, int Lca_fa, int l, int r, int d)
{
    if (l == r)
        return l;
    int mid = (l + r) >> 1;
    int left = Tree[Tree[x].lson].val + Tree[Tree[y].lson].val - Tree[Tree[Lca].lson].val - Tree[Tree[Lca_fa].lson].val;
    if (left >= d)
        return Query(Tree[x].lson, Tree[y].lson, Tree[Lca].lson, Tree[Lca_fa].lson, l, mid, d);
    else 
        return Query(Tree[x].rson, Tree[y].rson, Tree[Lca].rson, Tree[Lca_fa].rson, mid + 1, r, d - left);
}

int main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= N; ++i) scanf("%d", &A[i]), B[i] = A[i];
    sort(B + 1, B + N + 1);
    int sz = unique(B + 1, B + N + 1) - B - 1;
    int tmp;
    for (int i = 1; i <= N; ++i)tmp = lower_bound(B + 1, B + sz + 1, A[i]) - B, Re[tmp] = A[i], A[i] = tmp;
    for (int i = 1; i < N; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        add_edge(x, y);
        add_edge(y, x);
    }
    build(Root[0], 1, N);
    dep[1] = 1;
    dfs(1);
    for (int i = 1; i <= M; ++i)
    {
        int x, y, k;
        scanf("%d%d%d", &x, &y, &k);
        x ^= lastans;
        //v[x] + v[y] - v[Lca] - v[fa[Lca]]
        int Lca = lca(x, y);
        lastans = Re[Query(Root[x], Root[y], Root[Lca], Root[fa[Lca]], 1, N, k)];
        printf("%d\n", lastans);
    }
    return 0;
}