题目大意
就是给你一棵树，每个点都有点权，每次任意询问两点间路径上点权第k小的值（强制在线）。
思路分析
第k小。。。。。。又是主席树了。但这次变成树了，无法直接维护前缀和。
又是树上差分的小套路——每一个点到根的前缀和还是很好维护对吧。
询问(u,v)的时候，我们可以知道(size[root,u])和(size[root,v])的和。
但我们需要的只是一条路径，(lca(u,v))以上的全不要，(lca(u,v))也只要算一次。
于是用(size[root,u]+size[root,v]-size[root,lca(u,v)]-size[root,father(lca(u,v))])，也就是询问的时候四个点一起跳。
求LCA最方便的是倍增法（不会的百度一下），还有每个点对应的线段树从其父亲的线段树继承而来（根节点从(0)号空线段树继承而来），这两个操作我们在一次dfs建树时就可以一并处理完了。
话说我好久没打过倍增LCA了，老是写挂。。。。。。
闲话
另外，本蒟蒻听说倍增的二维数组把长度小的那一维度（即表示(2^j)的维度）开在前面会跑的快一些。
于是本蒟蒻亲自验证了一下，开在前面1112ms，开在后面992ms（没开O2，开了以后两个差不多）。。。。。。
这又是什么鬼？！
难道有评测机的不稳定因素？（洛谷一直很稳定啊！）
或者是有其他原因？欢迎各位大佬指教。
下面贴代码（开在前面）：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define R register int
#define G c=getchar()
#define in(Z) G;
while(c<'-')G;
Z=c&15;G;
while(c>'-')Z*=10,Z+=c&15,G;
const int N=100009,M=4000009;
int P,he[N],ne[N<<1],to[N<<1],f[18][N],d[N],b[N];
int n,SZ,a[N],g[N],rt[N],lc[M],rc[M],s[M];
void build(R&u,R l,R r){//建初始空线段树
u=++P;
if(l!=r){
R m=(l+r)>>1;
build(lc[u],l,m);
build(rc[u],m+1,r);
}
}
inline void insert(R*u,R v,R k){//更新
R l=1,r=SZ,m;
while(l!=r){
s[*u=++P]=s[v]+1;
m=(l+r)>>1;
if(k<=m)r=m,rc[*u]=rc[v],u=&lc[*u],v=lc[v];
else l=m+1,lc[*u]=lc[v],u=&rc[*u],v=rc[v];
}
s[*u=++P]=s[v]+1;
}
inline int ask(R u,R v,R w,R x,R k){//询问，四个点一起搞
R l=1,r=SZ,m,q;
while(l!=r){
m=(l+r)>>1;
q=s[lc[u]]+s[lc[v]]-s[lc[w]]-s[lc[x]];
if(k<=q)r=m,u=lc[u],v=lc[v],w=lc[w],x=lc[x];
else l=m+1,u=rc[u],v=rc[v],w=rc[w],x=rc[x],k-=q;
}
return g[l];
}
void dfs(R u,R fa){//建好树，顺便预处理LCA
d[u]=d[fa]+1;
f[0][u]=fa;
for(R&i=b[u];f[i+1][u]=f[i][f[i][u]];++i);
insert(&rt[u],rt[fa],lower_bound(g+1,g+SZ+1,a[u])-g);
for(R i=he[u];i;i=ne[i])
if(to[i]!=fa)dfs(to[i],u);
}
inline int getlca(R u,R v){//查LCA
R i;
if(d[u]<d[v])i=u,u=v,v=i;
for(i=b[u];d[u]>d[v]&&i>=0;--i)
if(d[f[i][u]]>=d[v])u=f[i][u];
for(i=b[u];i>=0;--i)
if(f[i][u]!=f[i][v])u=f[i][u],v=f[i][v];
return u==v?u:f[0][u];//这里老是忘记判
}
int main(){
register char c;
R p=1,m,i,u,v,k,lca,lans=0;
in(n);in(m);
for(i=1;i<=n;++i){in(a[i]);}
memcpy(g,a,(n+1)<<2);//搞出来离散化
sort(g+1,g+n+1);
SZ=unique(g+1,g+n+1)-g-1;
build(rt[0],1,SZ);
for(i=1;i<n;++i)
{
in(u);in(v);
to[++p]=v;ne[p]=he[u];he[u]=p;
to[++p]=u;ne[p]=he[v];he[v]=p;//建边
}
dfs(1,0);
while(m--){
in(u);in(v);in(k);
lca=getlca(u^=lans,v);
printf("%d
",lans=ask(rt[u],rt[v],rt[lca],rt[f[0][lca]],k));
}
return 0;
}