【CodeForces】191C Fools and Roads

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