BZOJ-2588: Spoj 10628. Count on

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2588

思路：

每个节点上建立一棵维护权值的可持久化线段树（维护从根到这个节点的权值），以他的父节点为历史版本建立，每次查询时直接在线段树上二分即可，所以只需要联立三棵可持久化线段树T[u],T[v],T[lca(u,v)]即可快捷查询。复杂度O(n log n)****

****代码：****

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

  

using namespace std;

  

#define MAXN 100001

  

int a[MAXN];

int n,m;

  

struct edge {

    int t;

    bool flag;

    edge *next;

    edge (){

        next=NULL;

        flag=false;

    }

} *head[MAXN];

  

void INSERT(int s,int t){

    edge *p=new(edge);

    p->t=t;

    p->next=head[s];

    head[s]=p;

}

  

struct Node {

    int l,r,mint;

} RMQ[MAXN*6];

  

int DFS[MAXN*2],V=0;

int h[MAXN],first[MAXN];

bool f[MAXN];

  

void dfs(int v){

    f[v]=false;

    DFS[++V]=v;

    first[v]=V;

    for (edge *p=head[v];p;p=p->next){

        if (f[p->t]){

            p->flag=true;

            h[p->t]=h[v]+1;

            dfs(p->t);

            DFS[++V]=v;

        }

    }

}

  

void Build_RMQ(int l,int r,int t){

    RMQ[t].l=l;

    RMQ[t].r=r;

    if (l==r){

        RMQ[t].mint=DFS[l];

        return ;

    }

    int mid=(l+r)>>1;

    Build_RMQ(l,mid,t<<1);

    Build_RMQ(mid+1,r,(t<<1)^1);

    if (h[RMQ[t<<1].mint]<h[RMQ[(t<<1)^1].mint]){

        RMQ[t].mint=RMQ[t<<1].mint;

    } else RMQ[t].mint=RMQ[(t<<1)^1].mint;

}

  

int query(int l,int r,int t){

    if (RMQ[t].l==l&&RMQ[t].r==r){

        return RMQ[t].mint;

    }

    int mid=(RMQ[t].l+RMQ[t].r)>>1;

    if (r<=mid) return query(l,r,t<<1);

    if (l>mid) return query(l,r,(t<<1)^1);

    int L=query(l,mid,t<<1),R=query(mid+1,r,(t<<1)^1);

    if (h[L]<h[R]) return L; else return R;

}

  

int lca(int s,int t){

    return query(min(first[s],first[t]),max(first[s],first[t]),1);

}

  

struct saver {

    int v,t;

} b[MAXN];

  

int c[MAXN],N=0;

int r[MAXN];

  

bool cmp(saver x,saver y){

    return x.v<y.v;

}

  

struct node {

    int l,r,s;

    node *left,*right;

    node (){

        s=0;

        left=right=NULL;

    }

} *T[MAXN];

  

void Build0(int l,int r,node *t){

    t->l=l;

    t->r=r;

    if (l==r) return ;

    Build0(l,(l+r)>>1,t->left=new(node));

    Build0(((l+r)>>1)+1,r,t->right=new(node));

}

  

  

void Add(int x,node *u,node *t){

    t->l=u->l;

    t->r=u->r;

    t->s=u->s+1;

    if (t->l==t->r) return ;

    int mid=(t->l+t->r)>>1;

    if (x<=mid) {

        t->right=u->right;

        t->left=new(node);

        Add(x,u->left,t->left);

    } else {

        t->left=u->left;

        t->right=new(node);

        Add(x,u->right,t->right);

    }

}

  

queue<int>Q;

  

void Build(){

    Build0(1,N,T[0]=new(node));

    INSERT(0,1);

    head[0]->flag=true;

    while (!Q.empty()) Q.pop();

    Q.push(0);

    while (!Q.empty()) {

        int v=Q.front();

        Q.pop();

        for (edge *p=head[v];p;p=p->next){

            if (p->flag){

                Add(r[p->t],T[v],T[p->t]=new(node));

                Q.push(p->t);

            }

        }

    }

}

  

int main(){

    scanf("%d%d",&n,&m);

    for (int i=0;i++<n;){

        scanf("%d",&a[i]);

    }

    memset(head,0,sizeof(head));

    for (int i=0;i++<n-1;){

        int s,t;

        scanf("%d%d",&s,&t);

        INSERT(s,t);

        INSERT(t,s);

    }

    memset(f,true,sizeof(f));

    h[1]=0;

    dfs(1);

    Build_RMQ(1,V,1);

    for (int i=0;i++<n;){

        b[i].v=a[i];

        b[i].t=i;

    }

    sort(b+1,b+n+1,cmp);

    c[++N]=b[1].v;

    r[b[1].t]=N;

    for (int i=1;i++<n;){

        if (b[i].v!=b[i-1].v){

            c[++N]=b[i].v;

        }

        r[b[i].t]=N;

    }

    Build();

    int lastans=0;

    while (m--){

        int u,v,k;

        scanf("%d%d%d",&u,&v,&k);

        u^=lastans;

        int L=lca(u,v);

        node *s=T[u],*t=T[v],*l=T[L];

        while (s->l!=s->r) {

            int sum=s->left->s+t->left->s-2*l->left->s;

            if (a[L]<=c[(s->l+s->r)>>1]&&a[L]>=c[s->l]) sum++;

            if (k<=sum) {

                s=s->left;

                t=t->left;

                l=l->left;

            } else {

                k-=sum;

                s=s->right;

                t=t->right;

                l=l->right;

            }

        }

        lastans=c[s->l];

        printf("%d",lastans);

        if (m) printf("\n");

    }

    return 0;

}