HDU 4010 Query on The Trees

Query on The Trees

Time Limit: 5000ms

Memory Limit: 65768KB

This problem will be judged on HDU. Original ID: 4010
64-bit integer IO format: %I64d Java class name: Main

We have met so many problems on the tree, so today we will have a query problem on a set of trees.
There are N nodes, each node will have a unique weight Wi. We will have four kinds of operations on it and you should solve them efficiently. Wish you have fun!

Input

There are multiple test cases in our dataset.
For each case, the first line contains only one integer N.(1 ≤ N ≤ 300000) The next N‐1 lines each contains two integers x, y which means there is an edge between them. It also means we will give you one tree initially.
The next line will contains N integers which means the weight Wi of each node. (0 ≤ Wi ≤ 3000)
The next line will contains an integer Q. (1 ≤ Q ≤ 300000) The next Q lines will start with an integer 1, 2, 3 or 4 means the kind of this operation.
1. Given two integer x, y, you should make a new edge between these two node x and y. So after this operation, two trees will be connected to a new one.
2. Given two integer x, y, you should find the tree in the tree set who contain node x, and you should make the node x be the root of this tree, and then you should cut the edge between node y and its parent. So after this operation, a tree will be separate into two parts.
3. Given three integer w, x, y, for the x, y and all nodes between the path from x to y, you should increase their weight by w.
4. Given two integer x, y, you should check the node weights on the path between x and y, and you should output the maximum weight on it.

Output

For each query you should output the correct answer of it. If you find this query is an illegal operation, you should output ‐1.
You should output a blank line after each test case.

Sample Input

Sample Output

3
-1
7

Hint

We define the illegal situation of different operations: In first operation: if node x and y belong to a same tree, we think it's illegal. In second operation: if x = y or x and y not belong to a same tree, we think it's illegal. In third operation: if x and y not belong to a same tree, we think it's illegal. In fourth operation: if x and y not belong to a same tree, we think it's illegal.

Source

The 36th ACM/ICPC Asia Regional Dalian Site —— Online Contest

解题：LCT

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int maxn = 300010;
  4 struct arc {
  5     int to,next;
  6     arc(int x = 0,int y = -1) {
  7         to = x;
  8         next = y;
  9     }
 10 } e[maxn<<1];
 11 int head[maxn],tot;
 12 void add(int u,int v) {
 13     e[tot] = arc(v,head[u]);
 14     head[u] = tot++;
 15 }
 16 struct LCT {
 17     int fa[maxn],ch[maxn][2],parent[maxn];
 18     int add[maxn],flip[maxn],maxv[maxn],key[maxn];
 19     void init() {
 20         memset(ch,0,sizeof ch);
 21         memset(fa,0,sizeof fa);
 22         flip[0] = flip[1] = 0;
 23         add[0] = add[1] = 0;
 24         parent[0] = parent[1] = 0;
 25         key[0] = maxv[0] = 0;
 26     }
 27     inline void pushup(int x) {
 28         maxv[x] = max(key[x],max(maxv[ch[x][0]],maxv[ch[x][1]]));
 29     }
 30     inline void inc(int x,int val) {
 31         if(!x) return;
 32         add[x] += val;
 33         key[x] += val;
 34         maxv[x] += val;
 35     }
 36     inline void pushdown(int x) {
 37         if(add[x]) {
 38             inc(ch[x][0],add[x]);
 39             inc(ch[x][1],add[x]);
 40             add[x] = 0;
 41         }
 42         if(flip[x]) {
 43             flip[ch[x][0]] ^= 1;
 44             flip[ch[x][1]] ^= 1;
 45             swap(ch[x][0],ch[x][1]);
 46             flip[x] = 0;
 47         }
 48     }
 49     void rotate(int x,int kd) {
 50         int y = fa[x];
 51         pushdown(y);
 52         pushdown(x);
 53         ch[y][kd^1] = ch[x][kd];
 54         fa[ch[x][kd]] = y;
 55         fa[x] = fa[y];
 56         ch[x][kd] = y;
 57         fa[y] = x;
 58         if(fa[x]) ch[fa[x]][y == ch[fa[x]][1]] = x;
 59         pushup(y);
 60     }
 61     void splay(int x,int goal = 0) {
 62         int y = x;
 63         pushdown(x);
 64         while(fa[y]) y = fa[y];
 65         if(x != y) {
 66             parent[x] = parent[y];
 67             parent[y] = 0;
 68             while(fa[x] != goal) {
 69                 pushdown(fa[fa[x]]);
 70                 pushdown(fa[x]);
 71                 pushdown(x);
 72                 if(fa[fa[x]] == goal) rotate(x,x == ch[fa[x]][0]);
 73                 else{
 74                     int y = fa[x],z = fa[y],s = (ch[z][0] == y);
 75                     if(x == ch[y][s]){
 76                         rotate(x,s^1);
 77                         rotate(x,s);
 78                     }else{
 79                         rotate(y,s);
 80                         rotate(x,s);
 81                     }
 82                 }
 83             }
 84         }
 85         pushup(x);
 86     }
 87     void access(int x){
 88         for(int y = 0; x; x = parent[x]){
 89             splay(x);
 90             fa[ch[x][1]] = 0;
 91             parent[ch[x][1]] = x;
 92             ch[x][1] = y;
 93             fa[y] = x;
 94             parent[y] = 0;
 95             y = x;
 96             pushup(x);
 97         }
 98     }
 99     void makeroot(int x){
100         access(x);
101         splay(x);
102         flip[x] ^= 1;
103     }
104     void join(int x,int y){
105         makeroot(x);
106         makeroot(y);
107         parent[x] = y;
108     }
109     int GetRoot(int x){
110         access(x);
111         splay(x);
112         while(ch[x][0]) x = ch[x][0];
113         return x;
114     }
115     void cut(int x){
116         access(x);
117         splay(x);
118         fa[ch[x][0]] = 0;
119         parent[ch[x][0]] = parent[x];
120         ch[x][0] = 0;
121         parent[x] = 0;
122         pushup(x);
123     }
124     void update(int x,int y,int val){
125         access(y);
126         for(y = 0; x; x = parent[x]){
127             splay(x);
128             if(!parent[x]){
129                 inc(ch[x][1],val);
130                 inc(y,val);
131                 key[x] += val;
132                 return;
133             }
134             fa[ch[x][1]] = 0;
135             parent[ch[x][1]] = x;
136             ch[x][1] = y;
137             fa[y] = x;
138             parent[y] = 0;
139             y = x;
140             pushup(x);
141         }
142     }
143     int query(int x,int y){
144         access(y);
145         for(y = 0; x; x = parent[x]){
146             splay(x);
147             if(!parent[x]) return max(max(maxv[ch[x][1]],maxv[y]),key[x]);
148             fa[ch[x][1]] = 0;
149             parent[ch[x][1]] = x;
150             ch[x][1] = y;
151             fa[y] = x;
152             parent[y] = 0;
153             y = x;
154             pushup(x);
155         }
156         return -1;
157     }
158 }lct;
159 void dfs(int u,int fa){
160     for(int i = head[u]; ~i; i = e[i].next){
161         if(e[i].to == fa) continue;
162         lct.parent[e[i].to] = u;
163         lct.add[e[i].to] = 0;
164         lct.flip[e[i].to] = 0;
165         dfs(e[i].to,u);
166     }
167 }
168 int main() {
169     int n,m,u,v,op,x,y,z;
170     while(~scanf("%d",&n)){
171         memset(head,-1,sizeof head);
172         tot = 0;
173         lct.init();
174         for(int i = 1; i < n; ++i){
175             scanf("%d%d",&u,&v);
176             add(u,v);
177             add(v,u);
178         }
179         dfs(1,1);
180         for(int i = 1; i <= n; ++i)
181             scanf("%d",&lct.key[i]);
182         scanf("%d",&m);
183         while(m--){
184             scanf("%d",&op);
185             if(op == 1){
186                 scanf("%d%d",&x,&y);
187                 if(lct.GetRoot(x) == lct.GetRoot(y)) puts("-1");
188                 else lct.join(x,y);
189             }else if(op == 2){
190                 scanf("%d%d",&x,&y);
191                 if(x == y || lct.GetRoot(x) != lct.GetRoot(y)) puts("-1");
192                 else{
193                     lct.makeroot(x);
194                     lct.cut(y);
195                 }
196             }else if(op == 3){
197                 scanf("%d%d%d",&z,&x,&y);
198                 if(lct.GetRoot(x) != lct.GetRoot(y)) puts("-1");
199                 else lct.update(x,y,z);
200             }else if(op == 4){
201                 scanf("%d%d",&x,&y);
202                 if(lct.GetRoot(x) != lct.GetRoot(y)) puts("-1");
203                 else printf("%d
",lct.query(x,y));
204             }
205         }
206         putchar('
');
207     }
208     return 0;
209 }

View Code