```
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <ctime>
#define maxn 100010
#define maxs 330
#define re register
#define FOR(i, l, r) for(re int i = l; i <= r; ++i)
using namespace std;
int n, m, c, r, t, x, y, k;
int sq1, sq2, num, cnt, col, theone, fh, lastans;
int a[maxn], b[maxn], depth[maxn], cnt1[maxs*2][maxs], cnt2[maxs*2][maxn];
int qwq[maxn], san1[maxn], san2[maxn], dis[maxn], head[maxn], numb[maxn];
int fa[maxn], siz[maxn], son[maxn], near[maxn], top[maxn], z[maxn], z1[maxn];
struct hz {
int next;
int to;
}h[maxn*2];
inline int read(){
int x=0;int f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c==-1) return 0;
if(c=='-')f=-1;
c=getchar();
}
while(c<='9'&&c>='0'){
x=(x<<1)+(x<<3)+(c^'0');
c=getchar();
}
return x*f;
}
inline void add(int from, int to) {
h[++num].next = head[from];
h[num].to = to;
head[from] = num;
}
void dfs1(int x, int f) {
fa[x] = f;
siz[x] = 1;
depth[x] = depth[f]+1;
for(re int i = head[x]; i != 0; i = h[i].next) {
if(h[i].to == f)
continue;
dfs1(h[i].to, x);
siz[x] += siz[h[i].to];
if(siz[h[i].to] > siz[son[x]])
son[x] = h[i].to;
}
}
void dfs2(int x, int topf) {
top[x] = topf;
if(!son[x])
return;
dfs2(son[x], topf);
for(re int i = head[x]; i != 0; i = h[i].next) {
if(h[i].to == fa[x] || h[i].to == son[x])
continue;
dfs2(h[i].to, h[i].to);
}
}
inline int lca(int x, int y) {
while(top[x] != top[y]) {
if(depth[top[x]] < depth[top[y]])
swap(x, y);
x = fa[top[x]];
}
if(depth[x] > depth[y])
swap(x, y);
return x;
}
void dfs3(int x, int color) {
if(numb[x] != 0)
color = numb[x];
near[x] = color;
for(re int i = head[x]; i != 0; i = h[i].next) {
if(h[i].to == fa[x])
continue;
dfs3(h[i].to, color);
}
}
inline void deal(int x, int times) {
while(x != 0) {
++cnt1[times][b[a[x]]];
++cnt2[times][a[x]];
x = fa[x];
}
}
int query(int x, int y, int k) {
if(near[x] == near[y]) {
int lc = lca(x, y), xx = x, yy = y, anss = 0;
while(x != lc)
++san1[b[a[x]]], ++san2[a[x]], x = fa[x];
while(y != fa[lc])
++san1[b[a[y]]], ++san2[a[y]], y = fa[y];
int tot = 0, now = 1;
while(tot+san1[now] < k)
tot += san1[now], ++now;
FOR(j, (now-1)*sq1+1, now*sq1)
if((tot += san2[j]) >= k) {
anss = z[j];
break;
}
while(xx != lc)
--san1[b[a[xx]]], --san2[a[xx]], xx = fa[xx];
while(yy != fa[lc])
--san1[b[a[yy]]], --san2[a[yy]], yy = fa[yy];
return anss;
}
int lc = lca(x, y), LC = lca(z1[near[x]], z1[near[y]]), xx = x, yy = y;
theone = -1, fh = 1;
if(lca(z1[near[x]], z1[near[y]]) == LC && (lca(lc, z1[near[x]]) == lc || lca(lc, z1[near[y]])) && lc != LC) { //需要转化加减答案
theone = lc;
san1[b[a[LC]]]--, san2[a[LC]]--;
}
while(near[fa[xx]] == near[x]) {
if(xx == theone) {
fh *= -1;
}
else {
san1[b[a[xx]]] += fh, san2[a[xx]] += fh;
}
if(xx == 0)
exit(0);
xx = fa[xx];
}
fh = 1;
while(near[fa[yy]] == near[y]) {
if(yy == theone) {
fh *= -1;
yy = fa[yy];
continue;
}
san1[b[a[yy]]] += fh, san2[a[yy]] += fh, yy = fa[yy];
}
++san1[b[a[LC]]];
++san2[a[LC]];
int tot = 0, now = 1, anss = 0;
while(tot+san1[now]+cnt1[near[x]][now]+cnt1[near[y]][now]-2*cnt1[numb[LC]][now] < k)
tot += san1[now]+cnt1[near[x]][now]+cnt1[near[y]][now]-2*cnt1[numb[LC]][now], ++now;
FOR(j, (now-1)*sq1+1, now*sq1)
if((tot += san2[j]+cnt2[near[x]][j]+cnt2[near[y]][j]-2*cnt2[numb[LC]][j]) >= k) {
anss = z[j];
break;
}
fh = -1, xx = x, yy = y;
while(near[fa[xx]] == near[x]) {
if(xx == theone) {
fh *= -1;
xx = fa[xx];
continue;
}
san1[b[a[xx]]] += fh, san2[a[xx]] += fh, xx = fa[xx];
}
fh = -1;
while(near[fa[yy]] == near[y]) {
if(yy == theone) {
fh *= -1;
yy = fa[yy];
continue;
}
san1[b[a[yy]]] += fh, san2[a[yy]] += fh, yy = fa[yy];
}
--san1[b[a[LC]]];
--san2[a[LC]];
if(lca(z1[near[x]], z1[near[y]]) == LC && (lca(lc, z1[near[x]]) == lc || lca(lc, z1[near[y]])) && lc != LC) { //需要转化加减答案
san1[b[a[LC]]]++, san2[a[LC]]++;
}
return anss;
}
signed main() {
srand(19260817);
srand(rand());
srand(rand());
n = read(), m = read();
FOR(i, 1, n) {
a[i] = read(), z[++z[0]] = a[i];
qwq[i] = i;
}
FOR(i, 1, n-1) {
x = read(), y = read();
add(x, y);
add(y, x);
}
sort(z+1, z+z[0]+1);
z[0] = unique(z+1, z+z[0]+1)-z-1;
FOR(i, 1, n)
a[i] = lower_bound(z+1, z+z[0]+1, a[i])-z;
sq1 = sqrt(z[0]);
FOR(i, 1, z[0])
b[i] = (i-1)/sq1+1;
random_shuffle(qwq+1, qwq+n+1);
sq2 = sqrt(n);
FOR(i, 1, sq2)
z1[++z1[0]] = qwq[i];
dfs1(1, 0);
dfs2(1, 1);
FOR(i, 1, sq2)
FOR(j, i+1, sq2)
z1[++z1[0]] = lca(qwq[i], qwq[j]);
sort(z1+1, z1+z1[0]+1);
z1[0] = unique(z1+1, z1+z1[0]+1)-z1-1;
FOR(i, 1, z1[0])
numb[z1[i]] = i;
dfs3(1, -2);
FOR(i, 1, z1[0])
deal(z1[i], i);
FOR(i, 1, m) {
x = read(), y = read(), k = read();
printf("%d\n", query(x, y, k));
}
}
```
by Juan_feng @ 2019-08-18 14:50:00
小学生发来惊讶的Orz
您竟然会我们不可望也不可及的算法
by yinxiaodi2006 @ 2019-08-18 14:51:45
算法正确性没有问题qwq 已经通过类似的题目了。
做法是往树里面撒关键点然后值域分块处理前缀信息， 查询的时候讨论一下就行了...
by Juan_feng @ 2019-08-18 14:53:04
@[Juan_feng](/space/show?uid=66965)
~~没事，我的主席树也UKE了~~
by Smile_Cindy @ 2019-08-18 14:53:38
SPOJ的问题，我在vjudge上也交不上去
by Smile_Cindy @ 2019-08-18 14:54:42
@[Alpha](/space/show?uid=87058) 我刚刚又交了一遍主席树过了... 交的树上莫队也不会UKE。。。 就针对我分块QAQ
by Juan_feng @ 2019-08-18 14:54:55
qwq
by chenxia25 @ 2019-08-18 14:54:56
原来用主席树A过一遍的
by Smile_Cindy @ 2019-08-18 14:55:16
注意： 我在短时间之内提交了多种代码。 其中只有我的分块uke了......
by Juan_feng @ 2019-08-18 14:55:32
@[Juan_feng](/space/show?uid=66965)
提交记录发一下
by Smile_Cindy @ 2019-08-18 14:56:14