题目描述

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 

HINT：

N,M<=100000

题目分析

树上主席树
判断时改一下差分策略

/**************************************************************
    Problem: 2588
    User: Superbia_zyb
    Language: C++
    Result: Accepted
    Time:5484 ms
    Memory:66184 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,cnt,tot;
int fa[100010][23];
int b[100010],c[100010],val[100010];
int head[100010],to[100010<<1],net[100010<<1];
void add(int x,int y)
{
    net[++tot]=head[x],head[x]=tot,to[tot]=y;
}
int getid(int x)
{
    return lower_bound(c+1,c+cnt+1,x)-c;
}
int root[100010],number,deep[100010];
struct your
{
    int lson,rson,sum;
}a[100010*40];
void update(int x,int &y,int l,int r,int c)
{
    y=++number;
    a[y]=a[x],a[y].sum++;
    if(l==r) return ;
    int mid=(l+r)>>1;
    if(c<=mid) update(a[x].lson,a[y].lson,l,mid,c);
    else update(a[x].rson,a[y].rson,mid+1,r,c);
}
void dfs(int x)
{
    update(root[fa[x][0]],root[x],1,cnt,getid(val[x]));
    deep[x]=deep[fa[x][0]]+1;
    for(int i=1;fa[x][i-1];i++)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=head[x];i;i=net[i])
        if(to[i]!=fa[x][0]) fa[to[i]][0]=x,dfs(to[i]);
}
int getlca(int x,int y)
{
    if(deep[x]<deep[y]) swap(x,y);
    for(int temp=19;temp>=0;temp--)
        if(deep[fa[x][temp]]>=deep[y]) x=fa[x][temp];
    if(x==y) return x;
    for(int temp=19;temp>=0;temp--)
        if(fa[x][temp]!=fa[y][temp]) x=fa[x][temp],y=fa[y][temp];
    return fa[x][0];
}
int ask(int x,int y,int z,int w,int l,int r,int k)
{
    if(l==r) return l;
    int mid=(l+r)>>1;
    int temp=a[a[x].lson].sum+a[a[y].lson].sum-a[a[z].lson].sum-a[a[w].lson].sum;
    if(temp>=k) return ask(a[x].lson,a[y].lson,a[z].lson,a[w].lson,l,mid,k);
    else return ask(a[x].rson,a[y].rson,a[z].rson,a[w].rson,mid+1,r,k-temp);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&val[i]),b[i]=val[i];
    sort(b+1,b+n+1);
    b[0]=-123456;
    for(int i=1;i<=n;i++)
        if(b[i]!=b[i-1]) c[++cnt]=b[i];
    for(int x,y,i=1;i<n;i++)
        scanf("%d%d",&x,&y),add(x,y),add(y,x);
    dfs(1);
    int ans=0;
    for(int x,y,k,i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&k),x^=ans;
        int lca=getlca(x,y),f=fa[lca][0];
        printf("");
        ans=c[ask(root[x],root[y],root[lca],root[f],1,cnt,k)];
        printf("%d",ans);
        if(i<m) printf("\n");
    }
    return 0;   
}