Description

给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v,k)，你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案，初始为0，即第一个询问的u是明文。

Input

第一行两个整数N,M。

第二行有N个整数，其中第i个整数表示点i的权值。

后面N-1行每行两个整数(x,y)，表示点x到点y有一条边。

最后M行每行两个整数(u,v,k)，表示一组询问。

Output

M行，表示每个询问的答案。最后一个询问不输出换行符

Sample Input

8 5

105 2 9 3 8 5 7 7

1 2

1 3

1 4

3 5

3 6

3 7

4 8

2 5 1

0 5 2

10 5 3

11 5 4

110 8 2

Sample Output

2

8

9

105

7

——————————————————————————

sb题（debug一晚上并且跨年的sb题）

没有考虑到根节点的爸爸是0所以犯了个sb错误。

直接考虑向根节点的每一条链上节点建主席树。

这样我们的delta就为sum[a]+sum[b]-sum[LCA(a,b)]-sum[father[lca(a,b)]]

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;typedef long long ll;const int N=100010;inline ll read(){ ll X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}struct tree{ int l; int r; int sum;}tr[N*20];struct node{ int to; int nxt;}edge[N*2];int a[N],b[N],rt[N],n,m,q,pool;int dep[N]={ 0},anc[N][30]={ 0};int cnt=0,head[N*2]={ 0};inline void add(int u,int v){ cnt++; edge[cnt].to=v; edge[cnt].nxt=head[u]; head[u]=cnt; return;}inline void LSH(){ sort(b+1,b+m+1); m=unique(b+1,b+m+1)-b-1; for(int i=1;i<=n;i++){ a[i]=lower_bound(b+1,b+m+1,a[i])-b; } return;}inline void insert(int y,int &x,int l,int r,int p){ tr[x=++pool]=tr[y];tr[x].sum++; if(l==r)return; int mid=(l+r)>>1; if(p<=mid)insert(tr[y].l,tr[x].l,l,mid,p); else insert(tr[y].r,tr[x].r,mid+1,r,p); return;}inline int query(int nl,int nr,int nm,int nfm,int l,int r,int k){ if(l==r)return l; int delta=tr[tr[nl].l].sum+tr[tr[nr].l].sum-tr[tr[nm].l].sum-tr[tr[nfm].l].sum; int mid=(l+r)>>1; if(delta>=k)return query(tr[nl].l,tr[nr].l,tr[nm].l,tr[nfm].l,l,mid,k); else return query(tr[nl].r,tr[nr].r,tr[nm].r,tr[nfm].r,mid+1,r,k-delta);}void dfs(int i){ dep[i]=dep[anc[i][0]]+1; insert(rt[anc[i][0]],rt[i],1,m,a[i]); for(int j=head[i];j;j=edge[j].nxt){ int k=edge[j].to; if(k!=anc[i][0]){ anc[k][0]=i; dfs(k); } } return;}int LCA(int i,int j){ if(dep[i]
            
             =0;k--){ if(dep[anc[i][k]]>=dep[j])i=anc[i][k]; } if(i==j)return i; for(int k=20;k>=0;k--){ if(anc[i][k]!=anc[j][k])i=anc[i][k],j=anc[j][k]; } return anc[i][0];}void LCAinit(){ for(int i=2;i<=n;i++){ int u=read(); int v=read(); add(u,v); add(v,u); } dfs(1); for(int j=1;j<=20;j++){ for(int i=1;i<=n;i++){ anc[i][j]=anc[anc[i][j-1]][j-1]; } } return;}int main(){ n=read(); q=read(); for(int i=1;i<=n;i++)a[i]=b[++m]=read(); LSH(); LCAinit(); int pre=0; for(int i=1;i<=q;i++){ int u=read()^pre,v=read(),k=read(); int t=LCA(u,v);int ft=anc[t][0]; printf("%d",pre=b[query(rt[u],rt[v],rt[t],rt[ft],1,m,k)]); if(i