2588: Spoj 10628. Count on a tree

时间：2022-12-01 19:12:18

2588: Spoj 10628. Count on a tree

Time Limit: 12 Sec  Memory Limit: 128 MB
Submit: 5766  Solved: 1374
[Submit][Status][Discuss]

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

HINT：
N,M<=100000
暴力自重。。。

Source

/*

树上第K大.

对于每一个节点以key（权值）为下标

用一颗权值线段树维护它到根的路径的区间K大值.

然后用主席树维护.

树剖求lca.

*/

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=1e5+,M=N*;

struct edge{int v,next;}e[N<<];int tot,head[N];

int n,m,sz,a[N],s[N],son[N],top[N],siz[N],fa[N],dep[N];

int root[N],sum[M],ls[M],rs[M];

int ans;

inline int read(){

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

void add(int x,int y){

    e[++tot].v=y;e[tot].next=head[x];head[x]=tot;

    e[++tot].v=x;e[tot].next=head[y];head[y]=tot;

}

//=========================================预处理

void insert(int &k,int last,int l,int r,int p){

    k=++sz;

    sum[k]=sum[last]+;

    if(l==r) return ;

    ls[k]=ls[last];

    rs[k]=rs[last];

    int mid=l+r>>;

    if(p<=mid) insert(ls[k],ls[last],l,mid,p);

    else insert(rs[k],rs[last],mid+,r,p);

}

int query(int l,int r,int x1,int x2,int x3,int x4,int K){

    if(l==r) return l;

    int mid=l+r>>;

    int cnt=sum[ls[x1]]+sum[ls[x2]]-sum[ls[x3]]-sum[ls[x4]];

    if(K<=cnt) return query(l,mid,ls[x1],ls[x2],ls[x3],ls[x4],K);

    else return query(mid+,r,rs[x1],rs[x2],rs[x3],rs[x4],K-cnt);

}

//=========================================主席树

void dfs(int x,int f,int de){

    fa[x]=f;dep[x]=de;siz[x]=;

    int p=lower_bound(s+,s+n+,a[x])-s;

    insert(root[x],root[f],,n,p);

    for(int i=head[x];i;i=e[i].next){

        if(e[i].v!=f){

            dfs(e[i].v,x,de+);

            siz[x]+=siz[e[i].v];

            if(siz[son[x]]<siz[e[i].v]) son[x]=e[i].v;

        }

    }

}

void getpos(int x,int tp){

    top[x]=tp;//pos[x]=++dfs_cnt;

    if(!son[x]) return ;

    getpos(son[x],tp);

    for(int i=head[x];i;i=e[i].next){

        if(e[i].v!=fa[x]&&e[i].v!=son[x]){

            getpos(e[i].v,e[i].v);

        }

    }

}

inline int lca(int x,int y){

    fa[]=;//求lca,fa[1]必须=1,否则就GG了

    for(;top[x]!=top[y];x=fa[top[x]]){

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

    }

    fa[]=;//当anc=1时,防止query(...root[anc],root[fa[anc]])出问题

    return dep[x]<dep[y]?x:y;

}

//=========================================树链剖分

void Q_ans(int x,int y,int K){

    int anc=lca(x,y);//类比区间[l,r]

    ans=query(,n,root[x],root[y],root[anc],root[fa[anc]],K);

    printf("%d",ans=s[ans]);

}

int main(){

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

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

    for(int i=,x,y;i<n;i++) x=read(),y=read(),add(x,y);

    sort(s+,s+n+);

    dfs(,,);getpos(,);

    for(int i=,x,y,z;i<=m;i++){

        x=read()^ans;y=read();z=read();

        Q_ans(x,y,z);

        if(i!=m) printf("\n");

    }

    return ;

}

相关文章