题意：给定一棵树,有点权,不带修改,询问路径点权第K大，强制在线。
这道题建主席树的方法好机智。按照BFS/DFS序建树，对于每个点，建出“这个点到根节点的路径上的点”组成的权值线段树,某个节点的树由父节点的树更改一条链得来。查询时用路径两个端点到根的线段树减去lca到根节点的线段树的2倍就得到了这条路径。注意lca的点权要特殊处理一下,不要把lca多减一次。据说只要分别减去lca和lca的父亲即可，查询的时候传4棵线段树的节点。
于是抖机灵强行传3个节点，单独处理lca,结果RE了一坨…..因为lca的权值小于区间中点的权值并不一定是lca处在[l,r]区间的左半部分，还有可能是lca在[l,r]区间的左边，加句rk[lca]>=l就过了.调了一小时,虚死….
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=;
int n,m;
struct edge{
int to,next;
}lst[maxn<<];int len=;
int first[maxn];
void addedge(int a,int b){
lst[len].to=b;
lst[len].next=first[a];
first[a]=len++;
}
int c[maxn];
int q[maxn];
int depth[maxn],p[maxn][];
void bfs(){
int head=,tail=;
depth[]=;
q[tail++]=;
int x;
while(head!=tail){
x=q[head++];
for(int pt=first[x];pt;pt=lst[pt].next){
if(lst[pt].to==p[x][])continue;
p[lst[pt].to][]=x;
depth[lst[pt].to]=depth[x]+;
q[tail++]=lst[pt].to;
}
for(int j=;p[x][j];++j)p[x][j+]=p[p[x][j]][j];
}
}
int LCA(int u,int v){
if(depth[u]<depth[v])swap(u,v);
for(int j=;j>=;--j){
if(depth[p[u][j]]>=depth[v])u=p[u][j];
}
if(u==v)return u;
for(int j=;j>=;--j){
if(p[u][j]!=p[v][j]){
u=p[u][j];v=p[v][j];
}
}
return p[u][];
}
struct node{
int sum;
node *lch,*rch;
node(){
lch=rch=;
sum=;
}
}t[maxn*];int cnt=;
int tot=;
node *root[maxn];
int qx;
int seq[maxn],dict[maxn],rk[maxn];
void Insert(node *rt1,node* &rt2,int l,int r){
++cnt;rt2=t+cnt;
if(l==r){
rt2->sum=rt1->sum+;
rt2->lch=rt2->rch=t+;
return;
}
int mid=(l+r)>>;
if(qx<=mid){
rt2->rch=rt1->rch;
Insert(rt1->lch,rt2->lch,l,mid);
}else{
rt2->lch=rt1->lch;
Insert(rt1->rch,rt2->rch,mid+,r);
}
rt2->sum=rt2->lch->sum+rt2->rch->sum;
}
void build_all(){
root[]=t+;
root[]->rch=root[]->lch=t+;
root[]->sum=;
for(int i=;i<n;++i){
qx=rk[q[i]];
Insert(root[p[q[i]][]],root[q[i]],,tot);
}
}
bool cmp(const int &x,const int &y){
return c[x]<c[y];
}
int lca;
int query(node *rt1,node *rt2,node *rt3,int l,int r){
if(l==r)return l;
int mid=(l+r)>>;
int lsum=rt1->lch->sum+rt2->lch->sum-*(rt3->lch->sum);
if(l<=rk[lca]&&rk[lca]<=mid)lsum++;
//if(rk[lca]<=mid) 错误的写法.这时rk[lca]可以小于l
if(qx<=lsum)return query(rt1->lch,rt2->lch,rt3->lch,l,mid);
else{
qx-=lsum;
return query(rt1->rch,rt2->rch,rt3->rch,mid+,r);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i){
scanf("%d",c+i);
seq[i]=i;
}
sort(seq+,seq+n+,cmp);
int old=c[seq[]]-;
for(int i=;i<=n;++i){
if(old!=c[seq[i]]){
old=c[seq[i]];++tot;
dict[tot]=c[seq[i]];
}
rk[seq[i]]=tot;
}
int a,b,k;
for(int i=;i<n;++i){
scanf("%d%d",&a,&b);
addedge(a,b);addedge(b,a);
}
bfs();
build_all();
int lastans=;
while(m--){
scanf("%d%d%d",&a,&b,&k);
a^=lastans;
qx=k;lca=LCA(a,b);
lastans=dict[query(root[a],root[b],root[lca],,tot)];
if(m)printf("%d\n",lastans);
else printf("%d",lastans);
}
return ;
}