11.10 game
题单介绍
### t1
给定长度为 $n$ 的序列 $a$，保证每个 $a_i$ 都能表示成正整数次幂的形式。
初始你有一个空的序列 $b$，你将依次对 $a_1,a_2,a_3,\cdots,a_n$ 进行操作。
每次对 $a_i$，可以选择【丢弃】或者【加入 $b$ 序列的末尾，然后重复将 $b$ 序列中相邻的两个相等的元素 $x$ 合并成 $2x$，直至不存在】。
输出任意操作后的 $b$ 序列最大值。
$1 \leq n \leq 10^5,1 \leq a_i \leq 10^9$。
注意到如果后来者更大，那么前者就不可能被合并，可以直接舍弃。
所以 $b$ 序列递减，直接单调栈即可，时间复杂度 $O(n)$。
```cpp
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#define FOR(i,a,b) for(int i = (a);i <= (b);++i)
#define REP(i,a,b) for(int i = (a);i >= (b);--i)
static char stkk[200];
template<typename T>inline void output(T x){
if(!x)return putchar('0'),void();
if(x<0)x = ~x+1,putchar('-');
int top = 0;
for(;x;stkk[++top]=x%10^48,x/=10);
for(;top;putchar(stkk[top--]));
}
template<typename T>inline void readx(T &x){
x = 0;int y = 1;char c = getchar();
for(;c<48||c>58;c = getchar())if(c=='-')y = -1;
for(;c>=48&&c<=58;c = getchar())x = (x<<1)+(x<<3)+(c^48);
x *= y;
}
const int N = 1e5+10;
static __int128 q[N];
static int tl,n;
inline void solve(){
__int128 x;
tl = 0;
readx(n);
FOR(i,1,n){
readx(x);
for(;tl&&q[tl-1]<x;--tl);
for(;tl&&q[tl-1]==x;x*=2,--tl);
q[tl++] = x;
}
output(q[0]),putchar(10);
}
signed main(){
freopen("merge.in","r",stdin);
freopen("merge.out","w",stdout);
int t;for(readx(t);t--;solve());
return 0;
}
```
### t2
```a,b,c``` 三人在打 ```icpc```。
有 $A$ 道简单题，$B$ 道中等题，$C$ 道困难题，总共有 $tot$ 分钟。
简单题耗时 $2$ 分钟，中等题耗时 $3$ 分钟，困难题耗时 $4$ 分钟。
每个选手解决题目分为思考和上机实现两部分，其中上机实现占题目总耗时的最后一分钟，其余时间为思考部分。
电脑在不能同时被超过两个选手占用；每个选手解决题目的时间必须连续，每个选手不能同时解决两到题目。
请最大化解决题目数并输出方案。
$1 \leq A,B,C,tot \leq 10^5$。
可以将完成一道题目视作占用一个结束时刻。
所以要让尽可能多的结束时刻被占用。
考虑贪心，如果能占用一个结束时刻就占用，答案一定不劣。
能占用的基础上，应当优先占用时间长的题目；占用题目时长固定的情况下，应当优先选择上一个结束时刻比较迟的人。
时间复杂度 $O(n)$。
```cpp
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#define FOR(i,a,b) for(int i = (a);i <= (b);++i)
#define REP(i,a,b) for(int i = (a);i >= (b);--i)
static char stkk[200];
template<typename T>inline void output(T x){
if(!x)return putchar('0'),void();
if(x<0)x = ~x+1,putchar('-');
int top = 0;
for(;x;stkk[++top]=x%10^48,x/=10);
for(;top;putchar(stkk[top--]));
}
template<typename T>inline void readx(T &x){
x = 0;int y = 1;char c = getchar();
for(;c<48||c>58;c = getchar())if(c=='-')y = -1;
for(;c>=48&&c<=58;c = getchar())x = (x<<1)+(x<<3)+(c^48);
x *= y;
}
const int N = 1e5+10,nf = 1e9+10;
struct node{int id,type;bool flg;}a[N];
static int ct[4],tot;
static int lt[4];
inline int get(int x){
int mi = -nf;
FOR(i,1,3)mi = std::max(mi,x-lt[i]);
mi = std::min(mi,4);
for(;mi>1&&!ct[mi-1];--mi);
return mi;
}
inline void solve(){
FOR(i,1,3)readx(ct[i]);
readx(tot);
int ans = 0;
FOR(i,1,tot){
int now = get(i);
if(now<2)continue;
int id = -1,pre = -1;
FOR(j,1,3)if(lt[j]+now<=i&&pre<lt[j])id = j,pre = lt[j];
a[i] = {id,now-1,1};
lt[id] = i,--ct[now-1],++ans;
}
output(ans),putchar(10);
FOR(i,1,tot)if(a[i].flg)output(a[i].id),putchar(' '),output(i-a[i].type-1),putchar(' '),output(i),putchar(10);
}
signed main(){
freopen("icpc.in","r",stdin);
freopen("icpc.out","w",stdout);
solve();
return 0;
}
```
### t3
定义一个区间对 $k$ 合法当且仅当区间内存在一个数出现次数大于等于 $k$。
给定长度为 $n$ 的序列 $a$，给定 $m$ 个询问，每次询问给定 $l,r,k$，求出将区间 $[l,r]$ 划分成若干**不重叠**的对 $k$ **合法**子区间数的最大值，如果 $[l,r]$ 不合法输出 ```0```。
$1 \leq n,m \leq 3 \times 10^5$。
时限 $8s$，空间 $512MB$。
先考虑暴力。
考虑直接贪心，对于固定 $k$ 的情况，每个 $i$，寻找一个最小的 $p_{i,k}$，使得 $[i,p_{i,k}]$ 对 $k$ 合法。
对于每个询问 $(l_i,r_i,k_i)$，每次就从 $l_i$ 跳到 $p_{l_i,k_i}+1$ 即可。
时间复杂度 $O(nq)$。
考虑对 $k$ 分治。
当 $k \leq B$ 时，暴力处理 $p_{i,k}$ 数组并且倍增，就能做到 $O(nB\log n)$ 预处理，$O(q\log n)$ 回答询问，如果对询问离线，并且统一处理 $k$ 相同的询问，空间就能从 $O(nB \log n)$ 优化到 $O(n \log n)$。
考虑查询和预处理的复杂度不平衡，类似 [P3203 [HNOI2010] 弹飞绵羊](https://www.luogu.com.cn/problem/P3203) 的分块，处理出每个点恰好跳出当前块的位置和步数，可以做到 $O(nB)$ 预处理，$O(q \sqrt n)$ 回答询问。
当 $k \gt B$ 时。
先预处理每个颜色 $c$ 对应的下标数组。
考虑暴力，对于每个 $l_i$，枚举出现次数为 $k$ 的元素 $c$，然后在 $c$ 对应的下标数组里面找到自 $l_i$ 开始出现次数等于 $k$ 的下标；取最小的合法下标，往后跳即可。
如果知道一个颜色 $c$ 大于 $l_i$ 的第一个位置 $j_{c,0}$，对于一个颜色 $c$ 的查询下标可以做到 $O(1)$；考虑对 $l_i$ 从左往右扫描线，$j_{c,0}$ 不降，所以可以做到 $O(1)$。
总共有 $q$ 个询问，每个询问至多跳 $\dfrac{n}{B}$ 次，至多有 $\dfrac{n}{B}$ 个有效颜色，所以时间复杂度是 $O(\dfrac{qn^2}{B^2})$。
视 $nq$ 同阶，综合复杂度，$B$ 取 $n^{\frac{2}{3}}$ 次方可以平衡到 $O(n^{\frac{5}{3}})$ 次方。
考虑更优雅的对 $k \gt B$ 的处理。
对每个颜色 $c$，维护 $j_{c,B}$ 表示当前颜色第 $B$ 个出现的下标位置。
枚举颜色时按 $j_{c,B}$ 从小到大枚举，然后如果 $res \leq j_{c,B}$ 时，由于 $j_{c,k} \geq j_{c,B}$，所以直接 ```break```。
考虑每个被枚举到的颜色都满足 $j_{c,B} \lt res$，所以被枚举到的颜色都会被跳过；每个被枚举的颜色都会至少贡献 $B$ 个被跳过的位置，所以枚举颜色数至多为 $O(\dfrac{n}{B})$。
对 $j_{c,B}$ 的维护可以 扫描线+```set```，总时间复杂度就可以平衡到 $O(n \sqrt n+ n \log n)$。
```cpp
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#define FOR(i,a,b) for(int i = (a);i <= (b);++i)
#define REP(i,a,b) for(int i = (a);i >= (b);--i)
#define ve std::vector
#define pb push_back
static char stkk[200];
template<typename T>inline void output(T x){
if(!x)return putchar('0'),void();
if(x<0)x = ~x+1,putchar('-');
int top = 0;
for(;x;stkk[++top]=x%10^48,x/=10);
for(;top;putchar(stkk[top--]));
}
template<typename T>inline void readx(T &x){
x = 0;int y = 1;char c = getchar();
for(;c<48||c>58;c = getchar())if(c=='-')y = -1;
for(;c>=48&&c<=58;c = getchar())x = (x<<1)+(x<<3)+(c^48);
x *= y;
}
const int N = 3e5+10,M = 20;
static int ans[N],a[N],n,m;
struct node1{int l,r,id;};
static ve<node1> qy1[N];
struct node2{int k,r,id;};
static ve<node2> qy2[N];
struct work1{
int ct[N],bl[N],r[N],jp[N],g[N],f[N],now;
void add(int x,int k){
(++ct[x])==k&&(++now);
}
void del(int x,int k){
(ct[x]--)==k&&(--now);
}
void solve(ve<node1> &qy,int k){
if(qy.empty())return;
now = 0;
// jp
for(int i = 1,j = 0;i <= n;del(a[i++],k)){
for(;j<n&&!now;add(a[++j],k));
if(now)jp[i] = j;
else jp[i] = n+1;
}
// f,g
REP(i,n,1){
if(jp[i]==n+1)f[i] = n+1;
if(jp[i]>=r[bl[i]])f[i] = jp[i],g[i] = 1;
else f[i] = f[jp[i]+1],g[i] = g[jp[i]+1]+1;
}
// qy
for(auto &t:qy){
int l = t.l,r = t.r,id = t.id,tmp = 0;
for(;l<=t.r;){
if(f[l]<=t.r)tmp+=g[l],l = f[l]+1;
else{
for(;l<=t.r;)
if(jp[l]<=t.r)++tmp,l = jp[l]+1;
else break;
break;
}
}
ans[id] = tmp;
}
}
void main(ve<node1> *qy,int B){
FOR(i,1,n)bl[i] = bl[i-1]+(i%B==1),r[bl[i]] = i;
FOR(i,2,B)solve(qy[i],i);
}
}t0;
struct work2{
std::set<int> s;
ve<int> f[N];
int ct[N];
inline void ckmin(int &x,int y){x>y&&(x=y);}
void main(ve<node2> *qy,int B){
// ct,f
FOR(i,1,n)f[a[i]].pb(i);
// s
FOR(i,1,n)if(f[i].size()>=B)s.insert(f[i][B-1]);
// qy
FOR(i,1,n){
for(auto &t:qy[i]){
int r = t.r,k = t.k,id = t.id,res = n+1;
for(auto &pr:s){
if(pr>=res)break;
if(f[a[pr]].size()>=ct[a[pr]]+k)ckmin(res,f[a[pr]][ct[a[pr]]+k-1]);
}
if(res<=t.r){
++ans[id];
if(res+B<=t.r)qy[res+1].pb(t);
}
}
if(f[a[i]].size()>=ct[a[i]]+B){
s.erase(f[a[i]][ct[a[i]]+B-1]);
if(f[a[i]].size()>=ct[a[i]]+1+B){
s.insert(f[a[i]][ct[a[i]]+B]);
}
}
++ct[a[i]];
}
}
}t1;
signed main(){
freopen("powder.in","r",stdin);
freopen("powder.out","w",stdout);
readx(n),readx(m);
int B = std::sqrt(n);
FOR(i,1,n)readx(a[i]);
for(int l,r,k,id = 1;id <= m;++id){
readx(l),readx(r),readx(k);
if(k==1)ans[id] = r-l+1;
else if(k<=B)qy1[k].pb((node1){l,r,id});
else qy2[l].pb((node2){k,r,id});
}
t0.main(qy1,B);
t1.main(qy2,B);
FOR(i,1,m)output(ans[i]),putchar(10);
return 0;
}
```
### t4
给定 $n$ 个节点的有点权的树和 $m$ 个询问，每次询问给定 $x,d,k$，输出树上距离点 $x$ 恰为 $d$ 的点中点权第 $k$ 小的点的编号，不存在输出 ```-1```。
保证点权互不相同。
$1 \leq n \leq q \leq 10^5$。
点分治+主席树/整体二分。
预处理各种下标可以做到 $O(n \log^2 n)$。
主席树的空间是 $O(n \log^2 n)$ 的，整体二分的空间是 $O(n \log n)$ 的；但是主席树的时间常数比整体二分小很多。
主席树：
```cpp
#include<bits/stdc++.h>
constexpr int rSiz=1<<21;
char rBuf[rSiz],*p1=rBuf,*p2=rBuf;
#define gc() (p1==p2&&(p2=(p1=rBuf)+fread(rBuf,1,rSiz,stdin),p1==p2)?EOF:*p1++)
template<class T>void rd(T&x){
char ch=gc();
for(;ch<'0'||ch>'9';ch=gc());
for(x=0;ch>='0'&&ch<='9';ch=gc())
x=(x<<1)+(x<<3)+(ch^48);
}
constexpr int _=1e5+5,__=4.2e7+5;
int n,m,q,a[_],b[_];
std::vector<int>e[_];
namespace LCA{
int dep[_],dfn[_],nfd[_<<1],cnt;
void dfs(int u,int fa){
dep[u]=dep[fa]+1;
nfd[dfn[u]=++cnt]=u;
for(int v:e[u])if(v^fa){
dfs(v,u);
nfd[++cnt]=u;
}
}
int argMin(int x,int y){return dep[x]<dep[y]?x:y;}
int w[19][_<<1],lg[_<<1];
int lca(int x,int y){
x=dfn[x],y=dfn[y];
if(x>y)std::swap(x,y);
int k=lg[y-x+1];
return argMin(w[k][x],w[k][y-(1<<k)+1]);
}
int dis(int x,int y){
return dep[x]+dep[y]-2*dep[lca(x,y)];
}
void init(){
dfs(1,0);lg[0]=-1;
for(int i=1;i<=cnt;++i)w[0][i]=nfd[i],lg[i]=lg[i>>1]+1;
for(int k=1;k<19;++k)for(int i=1;i+(1<<k)-1<=cnt;++i)
w[k][i]=argMin(w[k-1][i],w[k-1][i+(1<<(k-1))]);
}
}
using LCA::dis;
#define mid ((l+r)>>1)
struct node{int ls,rs,val;}t[__];
int cnt;
std::vector<int>tr[_][2];int ln[_][2];
void Chg(int &x,int l,int r,int w){
if(!x)t[x=++cnt]=t[0];
++t[x].val;if(l==r)return;
if(w<=mid)Chg(t[x].ls,l,mid,w);
else Chg(t[x].rs,mid+1,r,w);
}
void Ins(int u,int o,int d,int v){
// printf("%d %d %d %d %d\n",u,o,d,v,b[v]);
if(tr[u][o].empty())tr[u][o].resize(5,0);
if(ln[u][o]<d)tr[u][o].resize((ln[u][o]=d)+5,0);
Chg(tr[u][o][d],1,m,v);
}
bool vis[_];int fat[_];
int siz[_],mx[_],tot,cen;
void dfs1(int u,int fa){
siz[u]=1;mx[u]=0;
for(int v:e[u])if(!vis[v]&&v^fa){
dfs1(v,u);siz[u]+=siz[v];
mx[u]=std::max(mx[u],siz[v]);
}
mx[u]=std::max(mx[u],tot-siz[u]);
if(mx[u]<mx[cen])cen=u;
}
void dfs2(int u,int fa,int rt,int rf){
siz[u]=1;
Ins(rt,0,dis(u,rt),a[u]);
if(rf)Ins(rt,1,dis(u,rf),a[u]);
for(int v:e[u])if(!vis[v]&&v^fa)
dfs2(v,u,rt,rf),siz[u]+=siz[v];
}
void dfs3(int u,int fa){
tot=siz[u];mx[cen=0]=_;
dfs1(u,0);
vis[u=cen]=1;fat[u]=fa;
// printf("%d %d\n",u,fa);
dfs2(u,0,u,fa);
for(int v:e[u])if(!vis[v])dfs3(v,u);
}
std::vector<std::pair<int,int> >h;
void Fnd(int x,int d){
h.clear();int p=x;
for(;x;x=fat[x]){
// printf("%d %d %d %d\n",x,fat[x],ln[x][0],ln[x][1]);
int w=dis(p,x);
if(d>=w&&d-w<=ln[x][0])
h.push_back({tr[x][0][d-w],1});
if(fat[x]){
w=dis(p,fat[x]);
if(d>=w&&d-w<=ln[x][1])
h.push_back({tr[x][1][d-w],-1});
}
}
}
#define fio(x) freopen(x ".in","r",stdin);freopen(x ".out","w",stdout);
int main(){
fio("query");
rd(n),rd(q);
for(int i=1;i<=n;++i)rd(a[i]),b[i]=a[i];
std::sort(b+1,b+n+1);
m=std::unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;++i)a[i]=std::lower_bound(b+1,b+m+1,a[i])-b;
for(int i=1;i<=n;++i)b[a[i]]=i;
for(int i=1,u,v;i<n;++i)
rd(u),rd(v),e[u].push_back(v),e[v].push_back(u);
LCA::init();
t[0]={0,0,0};
siz[1]=n;
dfs3(1,0);
for(int i=1,x,d,k;i<=q;++i){
rd(x),rd(d),rd(k);
Fnd(x,d);
int l=1,r=m,v=0;
for(auto pr:h)v+=t[pr.first].val*pr.second;
if(v<k){printf("-1\n");continue;}
for(;l^r;){
v=0;
for(auto pr:h)v+=t[t[pr.first].ls].val*pr.second;
if(k<=v){
r=mid;
for(int i=0;i<(int)h.size();++i)h[i].first=t[h[i].first].ls;
}
else{
k-=v,l=mid+1;
for(int i=0;i<(int)h.size();++i)h[i].first=t[h[i].first].rs;
}
}
printf("%d\n",b[l]);
}
}
```
整体二分：
```cpp
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <cassert>
#define FOR(i,a,b) for(int i = (a);i <= (b);++i)
#define REP(i,a,b) for(int i = (a);i >= (b);--i)
static char stkk[200];
template<typename T>inline void output(T x){
if(!x)return putchar('0'),void();
if(x<0)x = ~x+1,putchar('-');
int top = 0;
for(;x;stkk[++top]=x%10^48,x/=10);
for(;top;putchar(stkk[top--]));
}
template<typename T>inline void readx(T &x){
x = 0;int y = 1;char c = getchar();
for(;c<48||c>58;c = getchar())if(c=='-')y = -1;
for(;c>=48&&c<=58;c = getchar())x = (x<<1)+(x<<3)+(c^48);
x *= y;
}
const int N = 1e5+10,M = 19,G = 1.7e6+10,nf = 2e9+10;
struct A{
#define GO(x) for(int i = h[x],y = e[i];i;y = e[i=ne[i]])
int e[N<<1],ne[N<<1],h[N],tot;
inline void add(int x,int y){e[++tot] = y,ne[tot] = h[x],h[x] = tot;}
int dfn[N],st[N][M],dep[N],dfsct;
void dfs0(int x,int fr){
st[dfn[x]=++dfsct][0] = fr;
dep[x] = dep[fr]+1;
GO(x)if(y^fr)dfs0(y,x);
}
int lg[N],pw[M];
inline void init_st(){
pw[0] = 1;
FOR(i,1,M-1)pw[i] = pw[i-1]<<1;
lg[0] = -1;
FOR(i,1,N-1)lg[i] = lg[i>>1]+1;
}
inline int get_min(int x,int y){
return dep[x]<dep[y]?x:y;
}
inline void init_lca(){
FOR(j,1,lg[dfsct])
FOR(i,1,dfsct-pw[j]+1)
st[i][j] = get_min(st[i][j-1],st[i+pw[j-1]][j-1]);
}
inline int lca(int x,int y){
if(x==y)return x;
if((x=dfn[x])>(y=dfn[y]))std::swap(x,y);
int k = lg[y-x++];
return get_min(st[x][k],st[y-pw[k]+1][k]);
}
inline int dis(int x,int y){
return dep[x]+dep[y]-(dep[lca(x,y)]<<1);
}
inline void bd_tr(){
dfs0(1,0);init_st(),init_lca();
}
inline void ckmax(int &x,int y){
x<y&&(x=y);
}
int sz[N],f[N];
bool vis[N];
void dfs1(int x,int fr,int &rt,int tot){
f[x] = 0,sz[x] = 1;
GO(x)if(!vis[y]&&y^fr){
dfs1(y,x,rt,tot),sz[x]+=sz[y];
ckmax(f[x],sz[y]);
}
ckmax(f[x],tot-sz[x]);
if(f[rt]>f[x])rt = x;
}
int fa[N],sz_rt[N];
int pld0[G],pld1[G],pls0[G],pls1[G];
int *d0[N],*d1[N],*s0[N],*s1[N],d0tp[N],d1tp[N];
int d0ct,d1ct,s0ct,s1ct;
int id0[N][M],id1[N][M];
inline void renew(int *p,int * &now,int &ct,int goal){
now = p+ct,ct+=goal+2;
}
void solve_rt(int x,int dep){
vis[x] = 1;sz_rt[x] = 1;
GO(x)if(!vis[y]){
int rt = 0;
f[rt] = sz[y];
dfs1(y,x,rt,sz[y]);
solve_rt(rt,dep+1);
fa[rt] = x,sz_rt[x]+=sz_rt[rt];
}
renew(pld0,d0[x],d0ct,sz_rt[x]),renew(pld1,d1[x],d1ct,sz_rt[x]);
renew(pls0,s0[x],s0ct,sz_rt[x]),renew(pls1,s1[x],s1ct,sz_rt[x]);
}
inline int lb(int *p,int tp,int v){
return std::lower_bound(p+1,p+1+tp,v)-p;
}
inline void add_x_dis(int x){
d0[x][++d0tp[x]] = 0;
for(int i = x;fa[i];i = fa[i]){
d1[i][++d1tp[i]] = d0[fa[i]][++d0tp[fa[i]]] = dis(x,fa[i]);
}
}
inline void rt_init_dis(int n){
FOR(i,1,n)add_x_dis(i);
FOR(i,1,n){
std::sort(d0[i]+1,d0[i]+1+d0tp[i]);
d0[i][++d0tp[i]] = nf;
d0tp[i] = std::unique(d0[i]+1,d0[i]+1+d0tp[i])-d0[i]-1;
if(d0[i][d0tp[i]]!=nf)puts("?"),exit(0);
std::sort(d1[i]+1,d1[i]+1+d1tp[i]);
d1[i][++d1tp[i]] = nf;
d1tp[i] = std::unique(d1[i]+1,d1[i]+1+d1tp[i])-d1[i]-1;
if(d1[i][d1tp[i]]!=nf)puts("?"),exit(0);
}
}
inline void add_qy_id(int x,int k,int *p0,int *p1){
int now_jp_ct = 0,pid,to;
pid = lb(d0[x],d0tp[x],k);
p0[0] = d0[x][pid]^k?-1:pid;
for(int i = x;fa[i];i = fa[i]){
++now_jp_ct;
pid = lb(d0[fa[i]],d0tp[fa[i]],to=k-dis(x,fa[i]));
p0[now_jp_ct] = d0[fa[i]][pid]^to?-1:pid;
pid = lb(d1[i],d1tp[i],to);
p1[now_jp_ct] = d1[i][pid]^to?-1:pid;
}
}
inline void add_x_id(int x,int *p0,int *p1){
int now_jp_ct = 0,pid,to;
p0[0] = lb(d0[x],d0tp[x],0);
for(int i = x;fa[i];i = fa[i]){
++now_jp_ct;
p0[now_jp_ct] = lb(d0[fa[i]],d0tp[fa[i]],to=dis(x,fa[i]));
p1[now_jp_ct] = lb(d1[i],d1tp[i],to);
}
}
inline void rt_init_id(int n){
FOR(i,1,n)add_x_id(i,id0[i],id1[i]);
}
inline void bd_rt(int n){
int rt = 0;f[rt] = n;
dfs1(1,0,rt,n);
solve_rt(rt,1);
rt_init_dis(n);
rt_init_id(n);
}
bool co[N];
inline void reve(int x,int *p0,int *p1){
int d = co[x]?-1:1,now_jp_ct = 0;
s0[x][p0[0]]+=d;
for(int i = x;fa[i];i = fa[i]){
++now_jp_ct;
s0[fa[i]][p0[now_jp_ct]]+=d;
s1[i][p1[now_jp_ct]]+=d;
}
co[x]^=1;
}
inline void my(int x){reve(x,id0[x],id1[x]);}
inline int qy(int x,int *p0,int *p1){
int ans = 0,now_jp_ct = 0;
if(~p0[0])ans+=s0[x][p0[0]];
for(int i = x;fa[i];i = fa[i]){
++now_jp_ct;
if(~p0[now_jp_ct])ans+=s0[fa[i]][p0[now_jp_ct]];
if(~p1[now_jp_ct])ans-=s1[i][p1[now_jp_ct]];
}
return ans;
}
#undef GO
}t0;
struct B{
int n,m,v[N],id_v[N];
struct node{int x,d,k,id;}qy[N],tmp[N];
int p0[N][M],p1[N][M];
bool flg[N];
inline void bd(){
//lca,dis
t0.bd_tr();
//rt
t0.bd_rt(n);
//p0,p1
FOR(i,1,m){
t0.add_qy_id(qy[i].x,qy[i].d,p0[i],p1[i]);
}
//init_rt
FOR(i,1,n)t0.my(i);
}
int p[N],a[N],ans[N];
inline void solve(int l,int r,int pl,int pr,node *qy){
if(l>r)return;
if(l==r){
FOR(i,pl,pr)if(t0.qy(qy[i].x,p0[qy[i].id],p1[qy[i].id])>=qy[i].k){
ans[qy[i].id] = id_v[l];
}
return;
}
int mid = (l+r)>>1;
FOR(i,mid+1,r)t0.my(id_v[i]);
FOR(i,pl,pr){
if(t0.qy(qy[i].x,p0[qy[i].id],p1[qy[i].id])>=qy[i].k){
ans[qy[i].id] = id_v[mid],flg[i] = 1;
}
else flg[i] = 0;
}
int tl = pl-1;
FOR(i,pl,pr)if(flg[i])tmp[++tl] = qy[i];
int tr = tl;
FOR(i,pl,pr)if(!flg[i])tmp[++tr] = qy[i];
FOR(i,pl,pr)qy[i] = tmp[i];
t0.my(id_v[mid]);
solve(l,mid-1,pl,tl,qy);
FOR(i,mid,r)t0.my(id_v[i]);
solve(mid+1,r,tl+1,pr,qy);
}
inline void main(){
//rd,add,v
readx(n),readx(m);
FOR(i,1,n)readx(v[i]),id_v[i] = i;
std::sort(id_v+1,id_v+1+n,[&](int x,int y){return v[x]<v[y];});
int tx,ty;FOR(i,2,n){
readx(tx),readx(ty);
t0.add(tx,ty),t0.add(ty,tx);
}
FOR(i,1,m){
p[i] = i;
readx(qy[i].x),readx(qy[i].d),readx(qy[i].k);
qy[i].id = i;
}
//bd()
bd();
//solve()
solve(1,n,1,m,qy);
FOR(i,1,m)output(ans[i]?ans[i]:-1),putchar(10);
}
}t1;
signed main(){
freopen("query.in","r",stdin);
freopen("query.out","w",stdout);
t1.main();
return 0;
}
```