You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
266 lines
6.7 KiB
C++
266 lines
6.7 KiB
C++
#define _CRT_SECURE_NO_WARNINGS
|
|
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING
|
|
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
const int N = 2e5 + 5;
|
|
#define cls(x) memset(x, 0, sizeof(x))
|
|
struct point
|
|
{
|
|
int l, r, w;
|
|
} c[N * 30];
|
|
int fa[N][25], a[N], h[N], tot, num, deep[N], n, m, rt[N], xxx, val[N];
|
|
int nxt[N << 1], head[N], go[N << 1];
|
|
inline int read()
|
|
{
|
|
int x;
|
|
scanf("%d", &x);
|
|
return x;
|
|
}
|
|
inline void insert(int y, int &x, int l, int r, int p)
|
|
{
|
|
c[x = ++num] = c[y];
|
|
c[x].w++;
|
|
if (l == r) return;
|
|
int mid = (l + r) >> 1;
|
|
if (p <= mid)
|
|
insert(c[y].l, c[x].l, l, mid, p);
|
|
else
|
|
insert(c[y].r, c[x].r, mid + 1, r, p);
|
|
c[x].w = c[c[x].l].w + c[c[x].r].w;
|
|
}
|
|
inline int query(int x, int y, int z, int d, int l, int r, int k)
|
|
{
|
|
if (l == r) return l;
|
|
int ret = c[c[x].l].w + c[c[y].l].w - c[c[z].l].w - c[c[d].l].w;
|
|
int mid = (l + r) >> 1;
|
|
if (k <= ret)
|
|
return query(c[x].l, c[y].l, c[z].l, c[d].l, l, mid, k);
|
|
else
|
|
return query(c[x].r, c[y].r, c[z].r, c[d].r, mid + 1, r, k - ret);
|
|
}
|
|
inline void add(int x, int y)
|
|
{
|
|
nxt[++tot] = head[x];
|
|
head[x] = tot;
|
|
go[tot] = y;
|
|
nxt[++tot] = head[y];
|
|
head[y] = tot;
|
|
go[tot] = x;
|
|
}
|
|
inline void dfs2(int u)
|
|
{
|
|
insert(rt[fa[u][0]], rt[u], 1, n, val[u]);
|
|
for (int i = head[u]; i; i = nxt[i])
|
|
{
|
|
int v = go[i];
|
|
if (v == fa[u][0]) continue;
|
|
dfs2(v);
|
|
}
|
|
}
|
|
inline void dfs(int u, int father)
|
|
{
|
|
deep[u] = deep[father] + 1;
|
|
for (int i = 0; i <= 20; i++)
|
|
fa[u][i + 1] = fa[fa[u][i]][i];
|
|
for (int i = head[u]; i; i = nxt[i])
|
|
{
|
|
int v = go[i];
|
|
if (v == father) continue;
|
|
fa[v][0] = u;
|
|
dfs(v, u);
|
|
}
|
|
}
|
|
inline int lca(int x, int y)
|
|
{
|
|
if (deep[x] < deep[y]) swap(x, y);
|
|
for (int i = 20; i >= 0; i--)
|
|
{
|
|
if (deep[fa[x][i]] >= deep[y])
|
|
x = fa[x][i];
|
|
if (x == y) return x;
|
|
}
|
|
for (int i = 20; i >= 0; i--)
|
|
{
|
|
if (fa[x][i] != fa[y][i])
|
|
{
|
|
x = fa[x][i];
|
|
y = fa[y][i];
|
|
}
|
|
}
|
|
return fa[x][0];
|
|
}
|
|
inline int find(int x)
|
|
{
|
|
int l = 1, r = xxx, mid;
|
|
while (l <= r)
|
|
{
|
|
mid = (l + r) >> 1;
|
|
if (x > h[mid])
|
|
l = mid + 1;
|
|
else
|
|
r = mid - 1;
|
|
}
|
|
return l;
|
|
}
|
|
int main()
|
|
{
|
|
int T = read();
|
|
while (T--)
|
|
{
|
|
/*int fa[N][25], a[N], h[N], tot, num, deep[N], n, m, rt[N], xxx, val[N];
|
|
int nxt[N << 1], head[N], go[N << 1];*/
|
|
cls(fa), cls(a), cls(h), cls(deep), cls(rt), cls(val), cls(nxt), cls(head), cls(go);
|
|
tot = num = 0;
|
|
int i, j, u, v, k;
|
|
n = read();
|
|
m = read();
|
|
for (i = 1; i <= n; i++)
|
|
{
|
|
val[i] = -read();
|
|
a[i] = val[i];
|
|
}
|
|
for (i = 1; i < n; i++)
|
|
{
|
|
u = read();
|
|
v = read();
|
|
add(u, v);
|
|
}
|
|
sort(a + 1, a + n + 1);
|
|
h[1] = a[1];
|
|
xxx = 1;
|
|
for (i = 2; i <= n; i++)
|
|
if (a[i] != a[i - 1]) h[++xxx] = a[i];
|
|
for (i = 1; i <= n; i++)
|
|
val[i] = find(val[i]);
|
|
dfs(1, 0);
|
|
int ans = 0;
|
|
dfs2(1);
|
|
for (i = 1; i <= m; i++)
|
|
{
|
|
u = read();
|
|
v = read();
|
|
k = read();
|
|
int z = lca(u, v);
|
|
int len = deep[u] - deep[z] + deep[v] - deep[z] + 1;
|
|
if (k > len)
|
|
ans = -1;
|
|
else
|
|
ans = -h[query(rt[u], rt[v], rt[z], rt[fa[z][0]], 1, n, k)];
|
|
printf("%d\n", ans);
|
|
}
|
|
}
|
|
return 0;
|
|
}
|
|
/*#define _CRT_SECURE_NO_WARNINGS
|
|
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING
|
|
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
const int N = 100011, NlogN = 2000011;
|
|
struct Tree
|
|
{
|
|
int ls, rs, sum;
|
|
#define ls(now) (tr[now].ls)
|
|
#define rs(now) (tr[now].rs)
|
|
#define sum(now) (tr[now].sum)
|
|
} tr[NlogN];
|
|
int rt[N];
|
|
int n, m, ans, a[N], b[N];
|
|
int x, y, p, k, cnt;
|
|
inline void disc_init()
|
|
{
|
|
sort(b + 1, b + b[0] + 1);
|
|
b[0] = unique(b + 1, b + b[0] + 1) - b - 1;
|
|
for (int i = 1; i <= n; i++)
|
|
a[i] = lower_bound(b + 1, b + b[0] + 1, a[i]) - b;
|
|
}
|
|
struct edge
|
|
{
|
|
int to;
|
|
edge *nxt;
|
|
#define VIS(now) for (edge *it = las[now]; it; it = it->nxt)
|
|
#define to(it) (it->to)
|
|
} e[N << 1], *las[N], *tot = e;
|
|
int top[N], fa[N], dep[N], sz[N];
|
|
inline void add(int x, int y)
|
|
{
|
|
*++tot = edge{y, las[x]}, las[x] = tot;
|
|
}
|
|
inline void dfs1(int now)
|
|
{
|
|
int to;
|
|
sz[now] = 1;
|
|
VIS(now)
|
|
if (!dep[to(it)])
|
|
{
|
|
dep[to(it)] = dep[now] + 1;
|
|
fa[to(it)] = now;
|
|
dfs1(to(it));
|
|
sz[now] += sz[to(it)];
|
|
}
|
|
}
|
|
inline void build(int cpy, int &now, int l, int r, int pos)
|
|
{
|
|
tr[now = ++cnt] = tr[cpy];
|
|
++sum(now);
|
|
if (l == r) return;
|
|
int mid = (l + r) >> 1;
|
|
pos <= mid ? build(ls(cpy), ls(now), l, mid, pos) : build(rs(cpy), rs(now), mid + 1, r, pos);
|
|
}
|
|
inline int query(int a, int b, int c, int d, int l, int r, int k)
|
|
{
|
|
if (l == r) return l;
|
|
int data = sum(ls(a)) + sum(ls(b)) - sum(ls(c)) - sum(ls(d));
|
|
int mid = (l + r) >> 1;
|
|
return k <= data ? query(ls(a), ls(b), ls(c), ls(d), l, mid, k) : query(rs(a), rs(b), rs(c), rs(d), mid + 1, r, k - data);
|
|
}
|
|
inline void dfs2(int now, int chain)
|
|
{
|
|
top[now] = chain;
|
|
build(rt[fa[now]], rt[now], 1, b[0], a[now]);
|
|
register int i = 0;
|
|
VIS(now)
|
|
if (fa[now] != (to(it)) && sz[to(it)] > sz[i]) i = to(it);
|
|
if (!i) return;
|
|
dfs2(i, chain);
|
|
VIS(now)
|
|
if (fa[now] != (to(it)) && i != to(it)) dfs2(to(it), to(it));
|
|
}
|
|
inline int lca(int x, int y)
|
|
{
|
|
for (; top[x] != top[y]; dep[top[x]] > dep[top[y]] ? x = fa[top[x]] : y = fa[top[y]])
|
|
;
|
|
return dep[x] < dep[y] ? x : y;
|
|
}
|
|
int main()
|
|
{
|
|
int T;
|
|
scanf("%d", &T);
|
|
while (T--)
|
|
{
|
|
scanf("%d%d", &n, &m);
|
|
for (int i = 1; i <= n; i++)
|
|
scanf("%d", a + i), b[++b[0]] = -a[i];
|
|
disc_init();
|
|
for (int i = 2; i <= n; i++)
|
|
{
|
|
scanf("%d%d", &x, &y);
|
|
add(x, y);
|
|
add(y, x);
|
|
}
|
|
dep[1] = 1;
|
|
dfs1(1);
|
|
dfs2(1, 1);
|
|
while (m--)
|
|
{
|
|
scanf("%d%d%d", &x, &y, &k);
|
|
p = lca(x, y);
|
|
int dis = dep[x] - dep[p] + dep[y] - dep[p] + 1;
|
|
if (k > dis)
|
|
ans = -1;
|
|
else
|
|
ans = -b[query(rt[x], rt[y], rt[p], rt[fa[p]], 1, b[0], k)];
|
|
printf("%d\n", ans);
|
|
}
|
|
}
|
|
return 0;
|
|
}*/ |