[HDU4010][LCT]Query on The Trees

Problem Description 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 5 1 2 2 4 2 5 1 3 1 2 3 4 5 6 4 2 3 2 1 2 4 2 3 1 3 5 3 2 1 4 4 1 4  

 

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   Recommend lcy   |   We have carefully selected several similar problems for you:   4004  4005  4006  4007  4001 [分析] 相当优美,巧妙的数据结构。 这题是入门题,关键在于区别lct的根和树的实根,以及转换上面。
  1 /*
  2 唐代白居易
  3 《浪淘沙·借问江潮与海水》
  4 借问江潮与海水,何似君情与妾心?
  5 相恨不如潮有信,相思始觉海非深。 
  6 */
  7 #include iostream
  8 #include cstdio
  9 #include algorithm
 10 #include cstring
 11 #include vector
 12 #include utility
 13 #include iomanip
 14 #include string
 15 #include cmath
 16 #include queue
 17 #include assert.h
 18 #include map
 19 #include ctime
 20 #include cstdlib
 21 #include stack
 22 #define LOCAL
 23 const int INF = 0x7fffffff;
 24 const int MAXN = 300000  + 10;
 25 const int maxnode = 1000000;
 26 const int maxm= 30000 * 2 + 10;
 27 using namespace std;
 28 
 29 struct Link_Cut_Tree{
 30        struct Node{//splay节点 
 31               int val, add;
 32               int Max, turn;
 33               Node *parent, *ch[2];
 34        }node[MAXN], *null;
 35        Node *pos;//计数
 36        Node *tmp[MAXN];
 37        
 38        void change(Node *u){access(u)-turn ^= 1;}//注意因为x是在右子树要翻转 
 39        void init(){
 40             //循环指针
 41             null = node;
 42             null-parent = null-ch[0] = null-ch[1] = null;
 43             null-Max = null-val = -INF;
 44             null-add = null-turn = 0;
 45             
 46             pos = node + 1;
 47        }
 48        //用这种方法实现快捷方便.便于直接查找 
 49        Node *NEW(int x){
 50             pos-Max = pos-val = x;
 51             pos-turn = pos-add = 0;
 52             pos-parent = pos-ch[0] = pos-ch[1] = null;
 53             return pos++;
 54        }
 55        //判断x是否是根,注意这个是判断是否是splay的根,而不是lct的根 
 56        bool is_root(Node *x){
 57             if (x == null || (x-parent-ch[0] != x  x-parent-ch[1] != x)) return 1;
 58             return 0;
 59        } 
 60        //标记下传 
 61        void pushdown(Node *x){
 62             if (x == null) return;
 63             if (x-turn){//翻转标记 
 64                
 65                if (x-ch[0] != null) x-ch[0]-turn ^= 1;
 66                if (x-ch[1] != null) x-ch[1]-turn ^= 1;
 67                swap(x-ch[0], x-ch[1]);//交换左右子树. 
 68                x-turn = 0;
 69             }
 70             //权值标记 
 71             if (x-add){
 72                if (x-ch[0] != null){
 73                   x-ch[0]-val += x-add;
 74                   x-ch[0]-Max += x-add;
 75                   x-ch[0]-add += x-add; 
 76                }
 77                if (x-ch[1] != null){
 78                   x-ch[1]-val += x-add;
 79                   x-ch[1]-Max += x-add;
 80                   x-ch[1]-add += x-add; 
 81                }
 82                x-add = 0;
 83             }
 84             return;
 85        }
 86        //更新 
 87        void update(Node *x){
 88             if (x == null) return;
 89             x-Max = max(x-val, max(x-ch[0]-Max, x-ch[1]-Max));
 90        }
 91       
 92        //d = 0为左旋,否则为右旋 
 93        void rotate(Node *x, int d){
 94             if (is_root(x)) return;//是根就不转
 95             Node *y = x-parent;
 96             y-ch[d ^ 1] = x-ch[d];
 97             if (x-ch[d] != null) x-ch[d]-parent = y; 
 98             x-parent = y-parent;
 99             if (y != null){
100                if (y == y-parent-ch[1]) y-parent-ch[1] = x;
101                else if (y == y-parent-ch[0]) y-parent-ch[0] = x;  
102             }
103             x-ch[d] = y;
104             y-parent = x;
105             update(y);
106        }
107        //将x转到根 
108        void splay(Node *x){
109             //带标记splay的伸展操作 
110             //将从顶部到根部的节点全部pushdown 
111             int cnt = 1;
112             tmp[0] = x;
113             for (Node *y = x; !is_root(y); y = y-parent) tmp[cnt++] = y-parent;
114             while (cnt) pushdown(tmp[--cnt]);
115             
116             while (!is_root(x)){
117                   Node *y = x-parent;
118                   if (is_root(y)) rotate(x, (x == y-ch[0]));
119                   else {
120                        int d = (y-parent-ch[0] == y);
121                        if (y-ch[d] == x) rotate(x, d ^ 1);
122                        else rotate(y, d);
123                        rotate(x, d);
124                   }
125             }
126             update(x);
127        }
128        //lct的访问操作,也是核心代码 
129        Node *access(Node *u){
130             Node *v = null;
131             while (u != null){//非lct根,总是放在右边 
132                   splay(u);
133                   v-parent = u;
134                   u-ch[1] = v;
135                   update(u);
136                   v = u;
137                   u = u-parent;
138             }
139             return v; 
140        }
141        //合并操作 
142        void merge(Node *u, Node *v){
143             //if (u-val == 2  v-val == 5)
144             //printf("%d\n", u-ch[0]-val);
145             //注意u为根
146             access(u);
147             splay(u);
148             
149             u-turn = 1;//翻转,因为在access之后,u已经成为splay中深度最大的点,因此右子树为null,此时要成为根就要翻转 
150             u-parent = v; 
151        } 
152        void cut(Node *u){
153             access(u);
154             splay(u);
155             //注意到u为根,自然深度最小,分离出来 
156             u-ch[0]-parent = null;
157             u-ch[0] = null;
158             update(u); 
159        }
160        //找根,不是真根 
161        Node *findroot(Node *u){
162             access(u);//不仅要打通,而且要让u成为根 
163             splay(u);
164             
165             while (u-parent != null) u = u-parent;
166             return u;
167        }
168        //判断u和v是否在同一个子树中 
169        bool check(Node *u, Node *v){
170             while (u-parent != null) u = u-parent;
171             while (v-parent != null) v = v-parent;
172             return (u == v);
173        }
174 }splay;
175 int u[MAXN],v[MAXN];
176 int n, m;
177 /*struct Node{
178        Node *ch[2];
179        int val;
180 };
181 Node* rotate(Node *t, int d){
182      Node *p = t-ch[d ^ 1];
183      t-ch[d ^ 1] = p-ch[d];
184      p-ch[d] = t;
185      t =  p;
186      return t; 
187 }*/
188 void init(){ 
189      splay.init();
190      for (int i = 1; i  n; i++) scanf("%d%d", u[i], v[i]);
191      //各点权值 
192      for (int i = 1; i = n; i++){
193          int t;
194          scanf("%d", t);
195          splay.NEW(t);
196      }
197      for (int i = 1; i  n; i++) {
198         // if (i == 3)
199         // printf("");
200          splay.merge(splay.node + u[i], splay.node + v[i]);
201          //printf("%d\n", splay.node[2].ch[0]-val);
202      }
203      //printf("%d", splay.check(splay.node + 4, splay.node + 5)); 
204 }
205 void work(){
206      scanf("%d", m);
207      for (int i = 1; i = m; i++){
208          int t;
209          scanf("%d", t);
210          if (t == 1){//连接两点 
211             int u, v;
212             scanf("%d%d", u, v);
213             //判断是否在同一个lct树内 
214             if (splay.check(splay.node + u, splay.node + v)){
215                //printf("%d ", i);
216                printf("-1\n");
217                continue;
218             }
219             splay.merge(splay.node + u, splay.node + v);
220          }else if (t == 2){
221             int u, v;
222             scanf("%d%d", u, v);
223             //分离两颗树 
224             if (u == v || !splay.check(splay.node + u, splay.node + v)){
225                //printf("%d ", i);
226                printf("-1\n");
227                continue;
228             } 
229             //转根再分离 
230             splay.change(splay.node + u);//注意这个根是原树的根不是lct的根 
231             splay.cut(splay.node + v);
232          }else if (t == 3){
233                int u, v, w;
234                scanf("%d%d%d", w, u, v);
235                //不再同一个树内自然无法更新 
236                if (!splay.check(splay.node + u, splay.node + v)){
237                   //printf("%d ", i);
238                   printf("-1\n");
239                   continue;
240                }
241                splay.change(splay.node + u);
242                splay.access(splay.node + v);
243                //将u换为真根,则u所在的splay都是v-u路径上的节点 
244                Link_Cut_Tree::Node *q = splay.findroot(splay.node + v);
245                q-add += w;
246                q-Max += w;
247                q-val += w;
248          }else {//查询操作 
249                int u, v;
250                scanf("%d%d", u, v);
251                if (!splay.check(splay.node + u, splay.node + v)){
252                   //printf("%d ", i);
253                   printf("-1\n");
254                   continue;
255                } 
256                //先换根 
257                splay.change(splay.node + u);
258                splay.access(splay.node + v);
259                printf("%d\n", splay.findroot(splay.node + v)-Max);
260          }
261      }
262      printf("\n");
263 }
264 
265 int main (){
266    
267     //scanf("%d", n);
268     while (scanf("%d", n) != EOF){
269           init();
270           work();
271     }
272     return 0;
273 }
View Code

 

转载于:https://www.cnblogs.com/hoskey/p/4342352.html

最新回复(0)
/jishuZn97iiEnNXcexf0o1LWTln9_2Bf2ozCsWAqKopD5ATBAo_3D4858418
8 简首页