希望更丰富的展现？使用Mark♂down
by aminoas @ 2019-03-16 20:38:06
@[2018J1605](/space/show?uid=143834) 第一次玩谢谢。好尴尬。。。。
by baozoudemolimao @ 2019-03-16 20:39:22
```
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
//#define scanf_s scanf
const int MAXN = 100090;
vector<int> child[MAXN + 5];
struct node {
int ls, rs, sum;
};
int father[MAXN + 5][18], value[MAXN + 5], num[MAXN + 5], depth[MAXN + 5], root[MAXN + 5];
node Tree[MAXN << 5];
int top = 0, cnt = 0;
void updata(int &now, int pre, int L, int R, int k, int n)
{
++top;
Tree[top] = Tree[pre];
now = top;
Tree[top].sum += n;
if (L == R) return;
int mid = (L + R) >> 1;
if (k <= mid) updata(Tree[now].ls, Tree[pre].ls, L, mid, k, n);
else updata(Tree[now].rs, Tree[pre].rs, mid + 1, R, k, n);
}
void dfs(int now)
{
depth[now] = depth[father[now][0]] + 1;
updata(root[now], root[father[now][0]], 1, cnt, num[now], 1);
int length = child[now].size(), t = 0;
for (int i = 0; i < length; ++i) {
t = child[now][i];
if (t == father[now][0]) continue;
father[t][0] = now;
dfs(t);
}
}
void make_father(int n)
{
for (int i = 1; i < 18; ++i) {
for (int j = 1; j <= n; ++j) {
father[j][i] = father[father[j][i - 1]][i - 1];
}
}
}
int ask(int u, int v, int lca, int lcaf, int L, int R, int k)
{
if (L == R) return L;
int sum = Tree[Tree[u].ls].sum + Tree[Tree[v].ls].sum - Tree[Tree[lca].ls].sum - Tree[Tree[lcaf].ls].sum;
int mid = (L + R) >> 1;
if (k <= sum) return ask(Tree[u].ls, Tree[v].ls, Tree[lca].ls, Tree[lcaf].ls, L, mid, k);
else return ask(Tree[u].rs, Tree[v].rs, Tree[lca].rs, Tree[lcaf].rs, mid + 1, R, k - sum);
}
int LCA(int a, int b) {
if (depth[a] > depth[b]) swap(a, b);
for (int i = 17; i >= 0; i--)
if (depth[father[b][i]] >= depth[a])
b = father[b][i];
if (a == b) return a;
for (int i = 19; i >= 0; i--) {
if (father[a][i] != father[b][i]) {
a = father[a][i];
b = father[b][i];
}
}
return father[a][0];
}
int main()
{
int n = 0, q = 0, from = 0, to = 0, ans = 0, lca = 0, k;
scanf_s("%d %d", &n, &q);
for (int i = 1; i <= n; ++i) {
scanf_s("%d", &num[i]);
value[i] = num[i];
}
sort(value + 1, value + n + 1);
cnt = unique(value + 1, value + n + 1) - value - 1;
for (int i = 1; i <= n; ++i) num[i] = lower_bound(value + 1, value + n + 1, num[i]) - value;
for (int i = 1; i < n; ++i) {
scanf_s("%d %d", &from, &to);
child[from].push_back(to);
child[to].push_back(from);
}
dfs(1);
for (int i = 1; i <= n; ++i) child[i].clear();
make_father(n);
while (q--) {
scanf_s("%d %d %d", &from, &to, &k);
from ^= ans;
lca = LCA(from, to);
ans = value[ask(root[from], root[to], root[lca], root[father[lca][0]], 1, cnt, k)];
printf("%d\n", ans);
}
}
```
by baozoudemolimao @ 2019-03-16 20:40:06
盖个楼
by baozoudemolimao @ 2019-03-17 13:29:33