题目描述
给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v,k)，你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案，初始为0，即第一个询问的u是明文。
输入格式
第一行两个整数N,M。
第二行有N个整数，其中第i个整数表示点i的权值。
后面N-1行每行两个整数(x,y)，表示点x到点y有一条边。
最后M行每行两个整数(u,v,k)，表示一组询问。
输出格式
M行，表示每个询问的答案。
输入输出样例
输入 #1
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
输出 #1
View Code
2 8 9 105 7
树上第k小
注意
注意主席树查询 x=t[lson[L]]+t[lson[R]]-t[lson[lca]]-t[lson[falca]];
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define pb push_back #define inf 0x3f3f3f3f #define pb push_back #define CLR(A,v) memset(A,v,sizeof A) typedef pair<int,int>pii; ////////////////////////////////// const int N=1e5+5; int a[N],b[N],T[N],lson[N<<5],rson[N<<5],t[N<<5],tot,c[N]; void upnode(int pre,int x,int l,int r,int &pos) { pos=++tot; lson[pos]=lson[pre],rson[pos]=rson[pre],t[pos]=t[pre]+1; if(l==r)return ;int m=(l+r)>>1; if(x<=m)upnode(lson[pre],x,l,m,lson[pos]); else upnode(rson[pre],x,m+1,r,rson[pos]); } int qsum(int L,int R,int lca,int falca,int k,int l,int r) { if(l==r)return l; int x=t[lson[R]]+t[lson[L]]-t[lson[lca]]-t[lson[falca]]; int m=(l+r)>>1; if(x>=k)return qsum(lson[L],lson[R],lson[lca],lson[falca],k, l,m); else return qsum(rson[L],rson[R],rson[lca],rson[falca],k-x, m+1,r); } /////////////////////////// int head[N],pos,id[N],top[N],fa[N],son[N],siz[N],dep[N],cnt; int n,m; struct Edge{int to,nex; } edge[N<<2]; inline void add(int a,int b) { edge[++pos]=(Edge){b,head[a]}; head[a]=pos; } void dfs1(int x,int f) { fa[x]=f;son[x]=0;siz[x]=1;dep[x]=dep[f]+1; upnode(T[f],c[x],1,n,T[x]); for(int i=head[x];i;i=edge[i].nex) { int v=edge[i].to;if(v==f)continue; dfs1(v,x);siz[x]+=siz[v]; if(siz[son[x]]<siz[v])son[x]=v; } } void dfs2(int x,int topf) { top[x]=topf; if(!son[x])return ; dfs2(son[x],topf); for(int i=head[x];i;i=edge[i].nex) { int v=edge[i].to; if(v==fa[x]||v==son[x])continue; dfs2(v,v); } } int getlca(int x,int y) { while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]])swap(x,y); x=fa[top[x]]; } return dep[x]>=dep[y]?y:x; } int q; int main() { RII(n,q); rep(i,1,n)RI(a[i]),b[i]=a[i]; sort(b+1,b+1+n); int m=unique(b+1,b+1+n)-b-1; rep(i,1,n) c[i]=lower_bound(b+1,b+1+m,a[i])-b; rep(i,1,n-1) { int u,v;RII(u,v);add(u,v);add(v,u); } dfs1(1,0);dfs2(1,1); int ans=0,lca; while(q--) { int x,y,k;RIII(x,y,k); x^=ans,lca=getlca(x,y); ans=b[ qsum(T[x],T[y],T[lca],T[fa[lca]],k,1,n)]; printf("%d ",ans); } return 0; }