| 12345678 |
- #include <algorithm>
- #include <array>
- #include <iostream>
- #include <queue>
- #include <vector>
- using namespace std;
- struct Node{int l=0,r=0,sum=0;};
- int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,q;cin>>n>>q;vector<int>w(n),vals;for(int&x:w)cin>>x;vals=w;sort(vals.begin(),vals.end());vals.erase(unique(vals.begin(),vals.end()),vals.end());vector<vector<int>>g(n);for(int i=1,u,v;i<n;++i){cin>>u>>v;--u;--v;g[u].push_back(v);g[v].push_back(u);}constexpr int LOG=17;vector<array<int,LOG+1>>up(n);vector<int>dep(n,-1),order;queue<int>que;dep[0]=0;que.push(0);while(!que.empty()){int u=que.front();que.pop();order.push_back(u);for(int v:g[u])if(dep[v]<0){dep[v]=dep[u]+1;up[v][0]=u;for(int j=1;j<=LOG;++j)up[v][j]=up[up[v][j-1]][j-1];que.push(v);}}vector<Node>tr(1);tr.reserve((n+1)*20);auto upd=[&](auto&&self,int old,int l,int r,int p)->int{int cur=tr.size();tr.push_back(tr[old]);++tr[cur].sum;if(l<r){int m=(l+r)/2;if(p<=m)tr[cur].l=self(self,tr[old].l,l,m,p);else tr[cur].r=self(self,tr[old].r,m+1,r,p);}return cur;};vector<int>root(n);for(int u:order){int pr=u==0?0:root[up[u][0]];root[u]=upd(upd,pr,0,vals.size()-1,lower_bound(vals.begin(),vals.end(),w[u])-vals.begin());}auto lca=[&](int a,int b){if(dep[a]<dep[b])swap(a,b);for(int j=LOG;j>=0;--j)if(dep[a]-(1<<j)>=dep[b])a=up[a][j];if(a==b)return a;for(int j=LOG;j>=0;--j)if(up[a][j]!=up[b][j])a=up[a][j],b=up[b][j];return up[a][0];};auto kth=[&](auto&&self,int A,int B,int C,int D,int l,int r,int k)->int{if(l==r)return l;int cnt=tr[tr[A].l].sum+tr[tr[B].l].sum-tr[tr[C].l].sum-tr[tr[D].l].sum,m=(l+r)/2;return k<=cnt?self(self,tr[A].l,tr[B].l,tr[C].l,tr[D].l,l,m,k):self(self,tr[A].r,tr[B].r,tr[C].r,tr[D].r,m+1,r,k-cnt);};while(q--){int a,b,k;cin>>a>>b>>k;--a;--b;int c=lca(a,b),d=c==0?0:root[up[c][0]];cout<<vals[kth(kth,root[a],root[b],root[c],d,0,vals.size()-1,k)]<<'\n';}}
|
