[Spoj 10628]Count on a tree

题目

给定一棵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

OUTPUT

2

8

9

105

7

解题报告

在树上建主席树

查询时二分查就行了

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 using namespace std;  6 inline int read(){  7     int sum(0);  8     char ch(getchar());  9     for(;ch<'0'||ch>'9';ch=getchar()); 10     for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar()); 11     return sum; 12 } 13 struct edge{ 14     int e; 15     edge *n; 16 }a[200005],*pre[100005]; 17 int tot; 18 inline void insert(int s,int e){ 19     a[++tot].e=e; 20     a[tot].n=pre[s]; 21     pre[s]=&a[tot]; 22 } 23 int timee; 24 int dep[100005],fa[100005][20],l[100005],r[100005],pos[100005]; 25 int n,m; 26 int cnt,size; 27 int v[100005],num[100005]; 28 int rt[100005],lch[2000005],rch[2000005],sum[2000005]; 29 inline void dfs(int u){ 30     l[u]=++timee; 31     pos[timee]=u; 32     for(int i=1;(1<
          
           <=dep[u];++i) 33         fa[u][i]=fa[fa[u][i-1]][i-1]; 34     for(edge *i=pre[u];i;i=i->n){ 35         int e(i->e); 36         if(e!=fa[u][0]){ 37             fa[e][0]=u; 38             dep[e]=dep[u]+1; 39             dfs(e); 40         } 41     } 42     r[u]=timee; 43 } 44 inline int lca(int x,int y){ 45     if(dep[x]
           
            0;++i) 49 if(delta&(1<
            
             =0;--i) 56 if(fa[x][i]!=fa[y][i]) 57 x=fa[x][i],y=fa[y][i]; 58 return fa[x][0]; 59 } 60 inline void build(int &x,int l,int r){ 61 x=++cnt; 62 sum[x]=0; 63 if(l==r) 64 return; 65 int mid((l+r)>>1); 66 build(lch[x],l,mid); 67 build(rch[x],mid+1,r); 68 } 69 inline void update(int &x,int las,int pos,int l,int r){ 70 x=++cnt; 71 lch[x]=lch[las]; 72 rch[x]=rch[las]; 73 sum[x]=sum[las]+1; 74 if(l==r) 75 return; 76 int mid((l+r)>>1); 77 if(pos<=mid) 78 update(lch[x],lch[las],pos,l,mid); 79 else 80 update(rch[x],rch[las],pos,mid+1,r); 81 } 82 inline int query(int x,int y,int k){ 83 int a(x),b(y),c(lca(x,y)),d(fa[c][0]); 84 a=rt[l[a]],b=rt[l[b]],c=rt[l[c]],d=rt[l[d]]; 85 int l(1),r(size); 86 while(l
             
              >1); 88 int tmp(sum[lch[a]]+sum[lch[b]]-sum[lch[c]]-sum[lch[d]]); 89 if(k<=tmp) 90 r=mid,a=lch[a],b=lch[b],c=lch[c],d=lch[d]; 91 else 92 k-=tmp,l=mid+1,a=rch[a],b=rch[b],c=rch[c],d=rch[d]; 93 } 94 return num[l]; 95 } 96 int ans; 97 int main(){ 98 memset(pre,NULL,sizeof(pre)); 99 n=read(),m=read();100 for(int i=1;i<=n;++i)101 num[i]=v[i]=read();102 for(int i=1;i