BZOJ2588 Count on a tree

题目描述

给定一棵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行，表示每个询问的答案。

输入样例：

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

输出样例：

2

8

9

105

7

说明

N,M<=100000

一道不错()的主席树练习题，因为主席树保存的是前缀和，这道题的题目框架是树形的，所以我们把一般的线性关系的主席树变成树形关系，再进行权值线段树的持久化就可以了。又因为对于两个节点(u,v)" role="presentation">(u,v)(u,v)，u到v路径上的数字个数可以表示成siz[u]+siz[v]−siz[lca(u,v)]−siz[fa[lca(u,v)]]" role="presentation">siz[u]+siz[v]−siz[lca(u,v)]−siz[fa[lca(u,v)]]siz[u]+siz[v]−siz[lca(u,v)]−siz[fa[lca(u,v)]]，根据这个性质我们就可以进行权值线段树上的二分了，注意书写细节即可()。

/*dream_maker*/

#include<bits/stdc++.h>

using namespace std;

#define N 200010

#define M 2000010

int read(){

    int ans=0,w=1;char c=getchar();

    while(c!='-'&&!isdigit(c))c=getchar();

    if(c=='-')w=-1,c=getchar();

    while(isdigit(c))ans=ans*10+c-'0',c=getchar();

    return ans*w;

}

int n,m,s,lastans=0,u,v,tot,cnt;

struct Edge{int v,next;}E[N<<1];

int head[N],a[N],b[N],fa[N][32],dep[N];

int rt[M]={0},ls[M]={0},rs[M]={0},siz[M]={0};

void add(int u,int v){

    E[++tot]=(Edge){v,head[u]};

    head[u]=tot;

}

void build(int &rt,int l,int r){

    if(l>r)return;

    rt=++cnt;

    if(l==r)return;

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

    build(ls[rt],l,mid);

    build(rs[rt],mid+1,r);

}

void modify(int &rt,int last,int l,int r,int val){

    rt=++cnt;

    siz[rt]=siz[last]+1;

    ls[rt]=ls[last];

    rs[rt]=rs[last];

    if(l==r)return;

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

    if(mid>=val)modify(ls[rt],ls[last],l,mid,val);

    else modify(rs[rt],rs[last],mid+1,r,val);

}

int query(int rt1,int rt2,int rt3,int rt4,int l,int r,int k){

    if(l==r)return l;

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

    int tmp=siz[ls[rt1]]+siz[ls[rt2]]-siz[ls[rt3]]-siz[ls[rt4]];

    if(tmp>=k)return query(ls[rt1],ls[rt2],ls[rt3],ls[rt4],l,mid,k);

    else return query(rs[rt1],rs[rt2],rs[rt3],rs[rt4],mid+1,r,k-tmp);

}

void dfs(int u,int f){

    fa[u][0]=f;

    modify(rt[u],rt[f],1,s,a[u]);

    dep[u]=dep[f]+1;

    for(int i=head[u];i;i=E[i].next){

        int v=E[i].v;

        if(v==f)continue;

        dfs(v,u);

    }

}

int Lca(int x,int y){

    if(dep[x]<dep[y])swap(x,y);

    int t=dep[x]-dep[y];

    for(int i=0;i<=31;i++)

        if((1<<i)&t)x=fa[x][i];

    if(x==y)return x;

    for(int i=31;i>=0;i--)

        if(fa[x][i]!=fa[y][i])

            x=fa[x][i],y=fa[y][i];

    return fa[x][0];

}

int main(){

//  freopen("2588.in","r",stdin);

//  freopen("2588.out","w",stdout);

    n=read();m=read();

    for(int i=1;i<=n;i++)b[i]=a[i]=read();

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

    s=unique(b+1,b+n+1)-b-1;

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

        u=read();v=read();

        add(u,v);add(v,u);

    }

    for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+s+1,a[i])-b;

    build(rt[0],1,s);

    dfs(1,0);

    int up=log2(n)+1;

    for(int k=1;k<=up;k++)

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

            fa[i][k]=fa[fa[i][k-1]][k-1];

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

        u=read();v=read();int k=read();

        u^=lastans;

        int lca=Lca(u,v);

        int ans=b[query(rt[u],rt[v],rt[lca],rt[fa[lca][0]],1,s,k)];

        printf("%d\n",ans);

        lastans=ans;

    }

    return 0;

}

siz