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
分析：
想用dfs序搞一下，套主席树
真的疯了，不知道怎么用主席树维护树上的一条链
开启喷人模式：
（以下是我在码码的时候的真实心理活动）
疯了吗
你知道在网上找到一篇可读的代码是多么难么
那些大佬都疯了吧，代码是人看的吗???
他们当初是怎么写出来的啊
dalao用nlogn的方法离散哼，
我要用O(n)的方法
哦哈哈哈哈，厉害了我自己
之后就是DFS，我的MA呀
在dfs里维护倍增
好吧，这好像是很nb的操作呢
完成了这些，我们就要构建主席树了呢
我的天哪，这一坨是什么啊
我们仔细看一下哈
在dfs的过程中，num已经变成了dfs序，
我们要做的就是按照dfs序进行添加
root[i]需要复制的节点是 ta的num的爸爸的编号代表的节点
（我的MA啊，这是什么，不管了。。。）
突然发现我和大佬代码的不同点
（废话，还能一模一样吗）
网上的代码insert是传入两个x,y
而我的处理方式简单一点，直接在insert之前
root[i]=root[fa[i]],完成复制
之后只传入root[i]
在处理询问的时候
我们把一条路径拆成两条链，
设两个点为a,b,c=lca(a,b),d=fa[c]
以前我们在区间上查询的时候判断的是
k和tree[tree[y].l].sum-tree[tree[x].l].sum
但是现在询问跑到了树上
我们需要比较k和
tree[tree[a].l].sum+tree[tree[b].l].sum-tree[tree[c].l].sum-tree[tree[d].l].sum
处理询问的时候用到了二分的思想
tip
insert的时候按照dfs序进行，所以传入的参数都是与num有关的
ask函数中
不要忘写k-=tmp
在bzoj上无限RE，真.束手无策。。。
这里写RE代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=150000;
const int lg=16;
struct node{
int l,r,sum;
};
node tree[N*40];
struct nd{
int x,y,nxt;
};
nd way[N<<1];
struct point{
int v,deep,fa[20],bh;
};
point po[N];
int n,m,tot=0,st[N],cnt=0,V[N],num[N],tt=0,root[N],id[N],val[N],top=0,ans=0;
int cmp(const int &a,const int &b){return V[a]<V[b];}
void add(int u,int w)
{
tot++;
way[tot].x=u;way[tot].y=w;way[tot].nxt=st[u];st[u]=tot;
tot++;
way[tot].x=w;way[tot].y=u;way[tot].nxt=st[w];st[w]=tot;
}
void dfs(int now,int f,int dep)
{
num[++cnt]=now; po[now].bh=cnt; //bh节点在主席树中的新编号
po[now].deep=dep;
po[now].fa[0]=f;
for (int i=1;i<=lg;i++)
if ((1<<i)<=dep)
po[i].fa[i]=po[po[i].fa[i-1]].fa[i-1];
else break;
for (int i=st[now];i;i=way[i].nxt)
if (way[i].y!=f)
dfs(way[i].y,now,dep+1);
}
void insert(int l,int r,int &now,int v)
{
top++;
tree[top]=tree[now];
now=top;
tree[now].sum++;
if (l==r) return;
int mid=(l+r)>>1;
if (v<=mid) insert(l,mid,tree[now].l,v);
else insert(mid+1,r,tree[now].r,v);
}
int lca(int x,int y)
{
if (po[x].deep<po[y].deep) swap(x,y);
int d=po[x].deep-po[x].deep;
if (d)
for (int i=0;i<=lg&&d;i++,d>>=1)
if (d&1)
x=po[x].fa[i];
if (x==y) return x;
for (int i=lg;i>=0;i--)
if (po[x].fa[i]!=po[y].fa[i]){
x=po[x].fa[i];y=po[y].fa[i];
}
return po[x].fa[0];
}
int ask(int x,int y,int k)
{
int a=x,b=y,c=lca(x,y),d=po[c].fa[0];
a=root[po[a].bh]; b=root[po[b].bh]; c=root[po[c].bh]; d=root[po[d].bh];
int l=1,r=tt,mid;
while (l<r)
{
mid=(l+r)>>1;
int tmp=tree[tree[a].l].sum+tree[tree[b].l].sum-tree[tree[c].l].sum-tree[tree[d].l].sum;
if (tmp>=k)
{
r=mid;
a=tree[a].l;b=tree[b].l;c=tree[c].l;d=tree[d].l;
}
else
{
k-=tmp; ///
l=mid+1;
a=tree[a].r;b=tree[b].r;c=tree[c].r;d=tree[d].r;
}
}
return val[l];
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
scanf("%d",&po[i].v);V[i]=po[i].v;id[i]=i;
}
sort(id+1,id+1+n,cmp);
tt=0;
for (int i=1;i<=n;i++){
if (V[id[i]]!=V[id[i-1]]) tt++; //完美的离散化
num[id[i]]=tt,val[tt]=V[id[i]]; //num[i] i现在排第几
}
for (int i=1;i<=n;i++) po[i].v=num[i];
for (int i=1;i<n;i++)
{
int u,w;
scanf("%d%d",&u,&w);
add(u,w);
}
cnt=0;
po[1].fa[0]=0; po[1].deep=1;
dfs(1,0,1);
root[0]=0;tree[0].l=tree[0].r=tree[0].sum=0;
for (int i=1;i<=n;i++)
{
root[i]=root[po[po[num[i]].fa[0]].bh];
insert(1,tt,root[i],po[num[i]].v);
}
while(m--)
{
int x,y,k;
scanf("%d%d%d",&x,&y,&k);
x^=ans;
ans=ask(x,y,k);
printf("%d
",ans);
}
return 0;
}