【SPOJ】2798 Query on a tree again!

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<queue>
  5 #define MAXN 100100
  6 #define MAXM 200100
  7 using namespace std;
  8 bool vis[MAXN];
  9 int e, first[MAXN], next[MAXM], v[MAXM];
 10 struct LCT {
 11     int bef[MAXN];
 12     int next[MAXN][2], pre[MAXN], key[MAXN], sum[MAXN];
 13     void Init() {
 14         memset(next, 0, sizeof(next));
 15         memset(pre, 0, sizeof(pre));
 16         memset(key, 0, sizeof(key));
 17         memset(sum, 0, sizeof(sum));
 18     }
 19     inline void PushUp(int x) {
 20         sum[x] = key[x] + sum[next[x][0]] + sum[next[x][1]];
 21     }
 22     inline void Rotate(int x, int kind) {
 23         int y, z;
 24         y = pre[x];
 25         z = pre[y];
 26         next[y][!kind] = next[x][kind];
 27         pre[next[x][kind]] = y;
 28         next[z][next[z][1] == y] = x;
 29         pre[x] = z;
 30         next[x][kind] = y;
 31         pre[y] = x;
 32         PushUp(y);
 33     }
 34     void Splay(int x) {
 35         int rt;
 36         for (rt = x; pre[rt]; rt = pre[rt])
 37             ;
 38         if (x != rt) {
 39             bef[x] = bef[rt];
 40             bef[rt] = 0;
 41             while (pre[x]) {
 42                 if (next[pre[x]][0] == x)
 43                     Rotate(x, 1);
 44                 else
 45                     Rotate(x, 0);
 46             }
 47             PushUp(x);
 48         }
 49     }
 50     void Access(int x) {
 51         int father;
 52         for (father = 0; x; x = bef[x]) {
 53             Splay(x);
 54             pre[next[x][1]] = 0;
 55             bef[next[x][1]] = x;
 56             next[x][1] = father;
 57             pre[father] = x;
 58             bef[father] = 0;
 59             father = x;
 60             PushUp(x);
 61         }
 62     }
 63     int Select(int x, int k) {
 64         while (!(sum[next[x][0]] + key[x] == k && key[x])) {
 65             if (sum[next[x][0]] + key[x] >= k)
 66                 x = next[x][0];
 67             else
 68                 x = next[x][1];
 69         }
 70         return x;
 71     }
 72     int Query(int x) {
 73         Access(x);
 74         Splay(1);
 75         if (sum[1])
 76             return Select(1, 1);
 77         return -1;
 78     }
 79     void Change(int x) {
 80         key[x] ^= 1;
 81         Splay(x);
 82     }
 83 } lct;
 84 int INT() {
 85     char ch;
 86     int res;
 87     while (ch = getchar(), !isdigit(ch))
 88         ;
 89     for (res = ch - '0'; ch = getchar(), isdigit(ch);)
 90         res = res * 10 + ch - '0';
 91     return res;
 92 }
 93 inline void AddEdge(int x, int y) {
 94     v[e] = y;
 95     next[e] = first[x];
 96     first[x] = e++;
 97 }
 98 void BFS(int x) {
 99     int i, y;
100     queue<int> q;
101     vis[x] = true;
102     q.push(x);
103     while (!q.empty()) {
104         x = q.front();
105         q.pop();
106         for (i = first[x]; i != -1; i = next[i]) {
107             y = v[i];
108             if (!vis[y]) {
109                 lct.bef[y] = x;
110                 vis[y] = true;
111                 q.push(y);
112             }
113         }
114     }
115 }
116 int main() {
117     int n, q, i, x, y;
118     while (~scanf("%d%d", &n, &q)) {
119         lct.Init();
120         memset(vis, false, sizeof(vis));
121         memset(first, -1, sizeof(first));
122         for (e = 0, i = 1; i < n; i++) {
123             x = INT(), y = INT();
124             AddEdge(x, y);
125             AddEdge(y, x);
126         }
127         BFS(1);
128         while (q--) {
129             x = INT(), y = INT();
130             if (x)
131                 printf("%d\n", lct.Query(y));
132             else
133                 lct.Change(y);
134         }
135     }
136     return 0;
137 }