【BZOJ2558】Count on a tree

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 using namespace std;
  7 int read(){int z=0,mark=1;  char ch=getchar();
  8     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)mark=-1;  ch=getchar();}
  9     while(ch>=‘0‘&&ch<=‘9‘){z=(z<<3)+(z<<1)+ch-‘0‘;  ch=getchar();}
 10     return z*mark;
 11 }
 12 struct ddd{int next,y;}e[210000];  int LINK[110000],ltop=0;
 13 inline void insert(int x,int y){e[++ltop].next=LINK[x];LINK[x]=ltop;e[ltop].y=y;}
 14 int n,m,a[110000];  int b[110000],disperse[110000],disperse_cnt=0;
 15 int ancestor[110000][20],deep[110000];
 16 int dfs_order[110000],order_cnt=0;
 17 struct dcd{int sleft,sright,mid,lchild,rchild,svalue;}tree[4100000];
 18 int roots[110000],tree_cnt=0;
 19 int get_SegmentTree(int x,int _left,int _right){
 20     tree[x].sleft=_left,tree[x].sright=_right,tree[x].mid=(_left+_right)>>1;
 21     tree[x].svalue=0;
 22     if(_left!=_right){
 23         tree[x].lchild=get_SegmentTree(++tree_cnt,_left,tree[x].mid);
 24         tree[x].rchild=get_SegmentTree(++tree_cnt,tree[x].mid+1,_right);
 25     }
 26     return x;
 27 }
 28 int modify(int x,int y){
 29     tree[++tree_cnt]=tree[x];  x=tree_cnt;  tree[x].svalue++;
 30     if(tree[x].sleft==y && tree[x].sright==y)  return x;
 31     if(y<=tree[x].mid)  tree[x].lchild=modify(tree[x].lchild,y);
 32     else  tree[x].rchild=modify(tree[x].rchild,y);
 33     return x;
 34 }
 35 /*int query(int x,int y,int z){
 36     if(tree[x].sleft==tree[x].sright)  return tree[x].sleft;
 37     else if(z<=tree[tree[y].lchild].svalue-tree[tree[x].lchild].svalue)
 38         return query(tree[x].lchild,tree[y].lchild,z);
 39     else  return query(tree[x].rchild,tree[y].rchild,
 40                        z-tree[tree[x].lchild].svalue+tree[tree[x].lchild].svalue);
 41 }*/
 42 int query(int x,int y,int z,int zz,int _value){
 43     if(tree[x].sleft==tree[x].sright)  return tree[x].sleft;
 44     int value_sum=tree[tree[x].lchild].svalue+tree[tree[y].lchild].svalue
 45         -tree[tree[z].lchild].svalue-tree[tree[zz].lchild].svalue;
 46     if(_value<=value_sum)  return query(tree[x].lchild,tree[y].lchild,tree[z].lchild,tree[zz].lchild,_value);
 47     else  return query(tree[x].rchild,tree[y].rchild,tree[z].rchild,tree[zz].rchild,_value-value_sum);
 48 }
 49 int binary_search(int x){
 50     int _left=1,_right=disperse_cnt,mid;
 51     while(_left+1<_right){
 52         mid=(_left+_right)>>1;
 53         if(disperse[mid]<=x)  _left=mid;
 54         else  _right=mid;
 55     }
 56     return (disperse[_right]==x)?_right:_left;
 57 }
 58 void dfs(int x){
 59     dfs_order[++order_cnt]=x;
 60     for(int i=1;(1<<i)<=deep[x];++i)  ancestor[x][i]=ancestor[ancestor[x][i-1]][i-1];
 61     for(int i=LINK[x];i;i=e[i].next)if(e[i].y!=ancestor[x][0]){
 62         ancestor[e[i].y][0]=x;  deep[e[i].y]=deep[x]+1;
 63         //roots[e[i].y]=modify(roots[x],binary_search(a[e[i].y]));
 64         dfs(e[i].y);
 65     }
 66 }
 67 int lca(int x,int y){
 68     if(deep[x]<deep[y])  swap(x,y);
 69     int _deep=deep[x]-deep[y];
 70     for(int i=0;i<=16;++i)if((1<<i)&_deep)  x=ancestor[x][i];
 71     for(int i=16;i>=0;--i)if(ancestor[x][i]!=ancestor[y][i])
 72         x=ancestor[x][i],y=ancestor[y][i];
 73     if(x==y)  return x;
 74     else return ancestor[x][0];
 75 }
 76 int main(){//freopen("ddd.in","r",stdin);
 77     cin>>n>>m;
 78     for(int i=1;i<=n;++i)  b[i]=a[i]=read();
 79     sort(b+1,b+n+1);
 80     for(int i=1;i<=n;++i)if(b[i]!=b[i-1])  disperse[++disperse_cnt]=b[i];
 81     int _left,_right,_value;
 82     for(int i=1;i<n;++i){
 83         _left=read(),_right=read();
 84         insert(_left,_right),insert(_right,_left);
 85     }
 86     roots[0]=get_SegmentTree(tree_cnt=0,1,disperse_cnt);
 87     insert(0,1);
 88     dfs(0);
 89     for(int i=1;i<=order_cnt;++i){
 90         int temp=dfs_order[i];
 91         roots[temp]=modify(roots[ancestor[temp][0]],binary_search(a[temp]));
 92     }
 93     int last=0;
 94     while(m --> 0){//趋向于
 95         _left=read(),_right=read(),_value=read();
 96         _left^=last;
 97         last=disperse[query(roots[_left],roots[_right],
 98                             roots[lca(_left,_right)],roots[ancestor[lca(_left,_right)][0]],_value)];
 99         printf("%d",last);
100         if(m)  printf("\n");
101     }
102     return 0;
103 }