【bzoj2588】Spoj 10628. Count on a tree

  1 #include <cstdio>
  2 #include <algorithm>
  3 #define N 100001
  4 using namespace std;
  5 struct data
  6 {
  7     int num , rank;
  8 }a[N];
  9 int root[N] , lp[N << 5] , rp[N << 5] , sum[N << 5] , val[N] , top , tot;
 10 int head[N] , to[N << 1] , next[N << 1] , cnt , fa[N] , bl[N] , deep[N] , si[N] , q[N] , tail;
 11 bool cmp1(data a , data b)
 12 {
 13     return a.num < b.num;
 14 }
 15 bool cmp2(data a , data b)
 16 {
 17     return a.rank < b.rank;
 18 }
 19 void add(int x , int y)
 20 {
 21     to[++cnt] = y;
 22     next[cnt] = head[x];
 23     head[x] = cnt;
 24 }
 25 void dfs1(int x)
 26 {
 27     int i;
 28     si[x] = 1;
 29     for(i = head[x] ; i ; i = next[i])
 30     {
 31         if(to[i] != fa[x])
 32         {
 33             fa[to[i]] = x;
 34             deep[to[i]] = deep[x] + 1;
 35             dfs1(to[i]);
 36             si[x] += si[to[i]];
 37         }
 38     }
 39 }
 40 void dfs2(int x , int c)
 41 {
 42     int i , k = 0;
 43     bl[x] = c;
 44     q[++tail] = x;
 45     for(i = head[x] ; i ; i = next[i])
 46         if(to[i] != fa[x] && si[to[i]] > si[k])
 47             k = to[i];
 48     if(k)
 49     {
 50         dfs2(k , c);
 51         for(i = head[x] ; i ; i = next[i])
 52             if(to[i] != fa[x] && to[i] != k)
 53                 dfs2(to[i] , to[i]);
 54     }
 55 }
 56 int getlca(int x , int y)
 57 {
 58     while(bl[x] != bl[y])
 59     {
 60         if(deep[bl[x]] < deep[bl[y]])
 61             swap(x , y);
 62         x = fa[bl[x]];
 63     }
 64     if(deep[x] < deep[y]) return x;
 65     return y;
 66 }
 67 void pushup(int x)
 68 {
 69     sum[x] = sum[lp[x]] + sum[rp[x]];
 70 }
 71 void ins(int x , int &y , int l , int r , int p)
 72 {
 73     y = ++tot;
 74     if(l == r)
 75     {
 76         sum[y] = sum[x] + 1;
 77         return;
 78     }
 79     int mid = (l + r) >> 1;
 80     if(p <= mid) rp[y] = rp[x] , ins(lp[x] , lp[y] , l , mid , p);
 81     else lp[y] = lp[x] , ins(rp[x] , rp[y] , mid + 1 , r , p);
 82     pushup(y);
 83 }
 84 int query(int a , int b , int c , int d , int l , int r , int p)
 85 {
 86     if(l == r) return val[l];
 87     int mid = (l + r) >> 1;
 88     if(sum[lp[a]] + sum[lp[b]] - sum[lp[c]] - sum[lp[d]] >= p) return query(lp[a] , lp[b] , lp[c] , lp[d] , l , mid , p);
 89     else return query(rp[a] , rp[b] , rp[c] , rp[d] , mid + 1 , r , p - sum[lp[a]] - sum[lp[b]] + sum[lp[c]] + sum[lp[d]]);
 90 }
 91 int main()
 92 {
 93     int n , m , i , x , y , z , f , last = 0;
 94     scanf("%d%d" , &n , &m);
 95     for(i = 1 ; i <= n ; i ++ )
 96     {
 97         scanf("%d" , &a[i].num);
 98         a[i].rank = i;
 99     }
100     sort(a + 1 , a + n + 1 , cmp1);
101     val[0] = 0x80000000;
102     for(i = 1 ; i <= n ; i ++ )
103     {
104         if(a[i].num != val[top]) val[++top] = a[i].num;
105         a[i].num = top;
106     }
107     sort(a + 1 , a + n + 1 , cmp2);
108     for(i = 1 ; i < n ; i ++ )
109     {
110         scanf("%d%d" , &x , &y);
111         add(x , y);
112         add(y , x);
113     }
114     dfs1(1);
115     dfs2(1 , 1);
116     for(i = 1 ; i <= tail ; i ++ )
117         ins(root[fa[q[i]]] , root[q[i]] , 1 , top , a[q[i]].num);
118     while(m -- )
119     {
120         scanf("%d%d%d" , &x , &y , &z);
121         x ^= last;
122         f = getlca(x , y);
123         last = query(root[x] , root[y] , root[f] , root[fa[f]] , 1 , top , z);
124         printf("%d" , last);
125         if(m) printf("\n");
126     }
127     return 0;
128 }