Bzoj 2588 Spoj 10628. Count on a tree(树链剖分LCA+主席树)

本文主要是介绍Bzoj 2588 Spoj 10628. Count on a tree(树链剖分LCA+主席树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2588: Spoj 10628. Count on a tree
Time Limit: 12 Sec Memory Limit: 128 MB
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
暴力自重。。。
Source
鸣谢seter

/*
树上第K大.
对于每一个节点
以key为下标
用一颗权值线段树维护它到根的路径的区间K大值.
然后用主席树维护.
树剖求lca.
ans=tree[x].size+tree[y].size-tree[lca].size-tree[lca_father].size.
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#define MAXN 100001
using namespace std;
int n,m,ans,cut,maxsize,root[MAXN],tot,s[MAXN],a[MAXN],head[MAXN];
int fa[MAXN],pos[MAXN],top[MAXN],deep[MAXN],size[MAXN];
struct data{int lc,rc,size;}tree[MAXN*20];
struct node{int v,next;}e[MAXN*2];
int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();return x*f;
}
void add(int u,int v)
{e[++cut].v=v;e[cut].next=head[u];head[u]=cut;
}
void add(int &k,int last,int l,int r,int x)
{k=++tot;tree[k].lc=tree[last].lc,tree[k].rc=tree[last].rc;tree[k].size=tree[last].size+1;if(l==r) return ;int mid=(l+r)>>1;if(x<=mid) add(tree[k].lc,tree[last].lc,l,mid,x);else add(tree[k].rc,tree[last].rc,mid+1,r,x);return ;
}
void dfs1(int u,int f)
{size[u]=1;int p=lower_bound(s+1,s+n+1,a[u])-s;add(root[u],root[f],1,n,p);for(int i=head[u];i;i=e[i].next){int v=e[i].v;if(v!=f) fa[v]=u,deep[v]=deep[u]+1,dfs1(v,u),size[u]+=size[v];}return ;
}
void dfs2(int u,int top1)
{int k=0;pos[u]=++maxsize;top[u]=top1;for(int i=head[u];i;i=e[i].next){int v=e[i].v;if(fa[v]==u&&size[v]>size[k]) k=v;}if(!k) return ;dfs2(k,top1);for(int i=head[u];i;i=e[i].next){int v=e[i].v;if(fa[v]==u&&v!=k) dfs2(v,v);}return ;
}
int lca(int x,int y)
{fa[1]=1;while(top[x]!=top[y]){if(deep[top[x]]<deep[top[y]]) swap(x,y);//1 R.x=fa[top[x]];}fa[1]=0;if(pos[x]>pos[y]) swap(x,y);return x;
}
int query(int L,int R,int lc,int falc,int l,int r,int k)
{if(l==r) return l;int mid=(l+r)>>1;int sum=tree[tree[L].lc].size+tree[tree[R].lc].size-tree[tree[lc].lc].size-tree[tree[falc].lc].size;if(sum>=k)return query(tree[L].lc,tree[R].lc,tree[lc].lc,tree[falc].lc,l,mid,k);else return query(tree[L].rc,tree[R].rc,tree[lc].rc,tree[falc].rc,mid+1,r,k-sum);
}
void slovequery(int x,int y,int k)
{int lc=lca(x,y);ans=query(root[x],root[y],root[lc],root[fa[lc]],1,n,k);printf("%d",ans=s[ans]);return ;
}
int main()
{int x,y,z;n=read(),m=read();for(int i=1;i<=n;i++) s[i]=a[i]=read();for(int i=1;i<=n-1;i++) x=read(),y=read(),add(x,y),add(y,x);sort(s+1,s+n+1);dfs1(1,0),dfs2(1,1),fa[1]=0;while(m!=1){x=read(),y=read(),z=read();x^=ans;slovequery(x,y,z);m--;printf("\n");//2 W.}x=read(),y=read(),z=read();x^=ans;slovequery(x,y,z);return 0;
}