题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2588
2588: Spoj 10628. Count on a tree
Time Limit: 12 Sec Memory Limit: 128 MB
Submit: 3584 Solved: 835
[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
题解：
在树上建主席树，记得最后一行后没有空格，否则PE.
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
struct node
{
int begin,end,next;
}edge[MAXN*];
struct NODE
{
int left,right;
}tree[MAXN*];
int cnt,Head[MAXN],n,SIZE,value[MAXN],pos[MAXN],deep[MAXN],P[MAXN][],sum[MAXN*],a[MAXN],val[MAXN],root[MAXN],tot;
bool vis[MAXN];
void addedge(int bb,int ee)
{
edge[++cnt].begin=bb;edge[cnt].end=ee;edge[cnt].next=Head[bb];Head[bb]=cnt;
}
void addedge1(int bb,int ee)
{
addedge(bb,ee);addedge(ee,bb);
}
int read()
{
int s=,fh=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}
return s*fh;
}
void dfs1(int u)
{
int i,v;
SIZE++;value[SIZE]=u;pos[u]=SIZE;
vis[u]=true;
for(i=Head[u];i!=-;i=edge[i].next)
{
v=edge[i].end;
if(vis[v]==false)
{
deep[v]=deep[u]+;
P[v][]=u;
dfs1(v);
}
}
}
void Ycl()
{
int i,j;
for(j=;(<<j)<=n;j++)
{
for(i=;i<=n;i++)
{
if(P[i][j-]!=-)P[i][j]=P[P[i][j-]][j-];
}
}
}
int LCA(int x,int y)
{
int i,j;
if(deep[x]<deep[y])swap(x,y);
for(i=;(<<i)<=deep[x];i++);i--;
for(j=i;j>=;j--)if(deep[x]-(<<j)>=deep[y])x=P[x][j];
if(x==y)return x;
for(j=i;j>=;j--)
{
if(P[x][j]!=-&&P[x][j]!=P[y][j])
{
x=P[x][j];
y=P[y][j];
}
}
return P[x][];
}
void Update(int x,int &y,int l,int r,int k)
{
y=++SIZE;
sum[y]=sum[x]+;
if(l==r)return;
tree[y].left=tree[x].left;tree[y].right=tree[x].right;
int mid=(l+r)/;
if(k<=mid)Update(tree[x].left,tree[y].left,l,mid,k);
else Update(tree[x].right,tree[y].right,mid+,r,k);
}
int query(int l,int r,int A,int B,int C,int D,int k)
{
if(l==r)return l;
int mid=(l+r)/,tmp=sum[tree[A].left]+sum[tree[B].left]-sum[tree[C].left]-sum[tree[D].left];
if(k<=tmp)return query(l,mid,tree[A].left,tree[B].left,tree[C].left,tree[D].left,k);
else return query(mid+,r,tree[A].right,tree[B].right,tree[C].right,tree[D].right,k-tmp);
}
int Query(int A,int B,int k)
{
int C=LCA(A,B),D=P[C][];
A=root[pos[A]];B=root[pos[B]];C=root[pos[C]];D=root[pos[D]];
return query(,tot,A,B,C,D,k);
}
int main()
{
int m,i,bb,ee,k,k1,lastans,U,V,K;
n=read();m=read();
for(i=;i<=n;i++)a[i]=val[i]=read();
sort(val+,val+n+);
tot=unique(val+,val+n+)-(val+);
memset(Head,-,sizeof(Head));cnt=;
for(i=;i<n;i++)
{
bb=read();ee=read();
addedge1(bb,ee);
}
memset(P,-,sizeof(P));SIZE=;
memset(value,,sizeof(value));//树上每个编号的实际的点.
memset(pos,,sizeof(pos));//每个点在树上的编号.
dfs1();Ycl();
memset(root,,sizeof(root));
SIZE=;
for(i=;i<=n;i++)//i为树上的节点.(即i为每个点在树上的编号.)
{
k=value[i];
k1=lower_bound(val+,val+tot+,a[k])-val;
Update(root[pos[P[k][]]],root[i],,tot,k1);
}
lastans=;
for(i=;i<=m;i++)
{
U=read();V=read();K=read();
U^=lastans;
lastans=val[Query(U,V,K)];
printf("%d",lastans);
if(i!=m)printf("\n");
}
fclose(stdin);
fclose(stdout);
return ;
}