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
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
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 ;
}