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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
| #include <queue>
#include <vector>
#include <cstdio>
#include <algorithm>
using std::vector;
const int MAXN = 100002, MAXDEEP = 20;
struct Edge
{
int v;
Edge *next;
} g[MAXN*2], *header[MAXN];
void AddEdge(const int x, const int y)
{
static int LinkSize;
Edge* const node = g+(LinkSize++);
node->v = y;
node->next = header[x];
header[x] = node;
}
int n, m, a[MAXN], p[MAXN][MAXDEEP], deep[MAXN];
vector<int> v;
void GetParent()
{
std::queue<int> Q;
for (Q.push(1); !Q.empty(); Q.pop())
{
const int u = Q.front();
deep[u] = deep[p[u][0]]+1;
for (int i = 1; i < MAXDEEP; ++i)
p[u][i] = p[p[u][i-1]][i-1];
for (Edge *e = header[u]; e; e = e->next)
if (p[u][0] != e->v)
p[e->v][0] = u, Q.push(e->v);
}
}
int GetLCA(int u, int v)
{
if (deep[u] < deep[v]) std::swap(u, v);
for (int i; deep[u] != deep[v]; u = p[u][i-1])
for (i = 1; deep[p[u][i]] >= deep[v]; ++i);
for (int i; u != v; u = p[u][i-1], v = p[v][i-1])
for (i = 1; p[u][i] != p[v][i]; ++i);
return v;
}
struct Node
{
int sum;
Node *lef, *rig;
} _memory[MAXN*MAXDEEP*2], *root[MAXN*2+1];
int _memory_size, _st, _ed, _x, dfn[MAXN*2];
Node* _new_archive(Node* const pre, const int lef, const int rig)
{
Node* const node = _memory+(_memory_size++);
node->sum = pre->sum + _x;
node->lef = pre->lef;
node->rig = pre->rig;
if (lef == rig) return node;
const int mid = (lef+rig)/2;
if (_st <= mid) node->lef = _new_archive(pre->lef, lef, mid);
if (mid+1 <= _ed) node->rig = _new_archive(pre->rig, mid+1, rig);
node->sum = node->lef->sum + node->rig->sum;
return node;
}
int _query(Node* const pre, Node* const lca, Node* const u, Node* const v, const int lef, const int rig)
{
if (lef == rig) return lef;
const int mid = (lef+rig)/2;
const int cnt = u->lef->sum + v->lef->sum - lca->lef->sum - pre->lef->sum;
if (_x <= cnt) return _query(pre->lef, lca->lef, u->lef, v->lef, lef, mid);
_x -= cnt;
return _query(pre->rig, lca->rig, u->rig, v->rig, mid+1, rig);
}
Node* NewArchive(Node* const pre, const int pos, const int delta)
{
_st = _ed = pos, _x = delta;
return _new_archive(pre, 1, n);
}
int Query(const int pre, const int lca, const int u, const int v, const int k)
{
_x = k;
return _query(root[dfn[pre]], root[dfn[lca]], root[dfn[u]], root[dfn[v]], 1, n);
}
Node* Build(const int lef, const int rig)
{
Node* const node = _memory+(_memory_size++);
node->sum = 0;
if (lef == rig) return node;
const int mid = (lef+rig)/2;
node->lef = Build(lef, mid);
node->rig = Build(mid+1, rig);
return node;
}
void DFSBuild(const int u)
{
static int version;
dfn[u] = ++version;
root[version] = NewArchive(root[version-1], a[u], +1);
for (Edge *e = header[u]; e; e = e->next)
if (e->v != p[u][0])
DFSBuild(e->v);
++version;
root[version] = NewArchive(root[version-1], a[u], -1);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
{
scanf("%d", a+i);
v.push_back(a[i]);
}
std::sort(v.begin(), v.end());
v.resize(std::unique(v.begin(), v.end())-v.begin());
for (int i = 1; i <= n; ++i)
a[i] = std::lower_bound(v.begin(), v.end(), a[i])-v.begin()+1;
for (int i = 1, x, y; i < n; ++i)
{
scanf("%d%d", &x, &y);
AddEdge(x, y);
AddEdge(y, x);
}
GetParent();
root[0] = Build(1, n);
DFSBuild(1);
for (int i = 0, last = 0, x, y, k; i < m; ++i)
{
scanf("%d%d%d", &x, &y, &k);
x ^= last;
const int lca = GetLCA(x, y);
if (i) printf("\n");
printf("%d", last = v[Query(p[lca][0], lca, x, y, k)-1]);
}
}
|
