首页 > > 程序设计 > C/C++ >

HDU4010 Query on The Trees （LCT动态树）

2018-06-17 21:25:52来源：未知阅读 ()

Query on The Trees

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 6447 Accepted Submission(s): 2547

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.

题意

给出一颗树，有4种操作：

如果x和y不在同一棵树上，则在x，y之间连一条边
如果x和y在同一棵树上，并且x!=y，则把x换为树根，并把y和其父亲分离
如果x和y在同一棵树上，则x到y的路径上所有的点权值加上w
如果x和y在同一棵树上，则输出x到y路径上的最大值

code

LCT —— 神奇的数据结构

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cstring>
  4 
  5 using namespace std;
  6 
  7 const int N = 300100;
  8 int ch[N][2],fa[N],val[N],add[N],rev[N],mx[N],head[N];
  9 int st[N],top,n,m,tot;
 10 struct Edge{
 11     int to,nxt;
 12 }e[N<<1];
 13 
 14 inline int read() {
 15     int x = 0,f = 1;char ch = getchar();
 16     for (; ch<'0'||ch>'9'; ch = getchar()) if (ch=='-') f = -1;
 17     for (; ch>='0'&&ch<='9'; ch = getchar()) x = x * 10 + ch - '0';
 18     return x * f;
 19 }
 20 void add_edge(int u,int v) {
 21     e[++tot].to = v,e[tot].nxt = head[u],head[u] = tot;
 22 }
 23 void pushup(int x) {
 24     mx[x] = max(max(mx[ch[x][0]],mx[ch[x][1]]),val[x]);
 25 }
 26 void pushdown(int x) {
 27     int l = ch[x][0],r = ch[x][1];
 28     if (rev[x]) {
 29         rev[l] ^= 1;rev[r] ^= 1;
 30         swap(ch[x][0],ch[x][1]);
 31         rev[x] ^= 1;
 32     }
 33     if (add[x]) {
 34         if (l) add[l] += add[x],mx[l] += add[x],val[l] += add[x];
 35         if (r) add[r] += add[x],mx[r] += add[x],val[r] += add[x];
 36         add[x] = 0;
 37     }
 38 }
 39 bool isroot(int x) {
 40     return ch[fa[x]][0]!=x && ch[fa[x]][1]!=x;
 41 }
 42 inline int son(int x) {
 43     return ch[fa[x]][1]==x;
 44 }
 45 void rotate(int x) {
 46     int y = fa[x],z = fa[y],b = son(x),c = son(y),a = ch[x][!b];
 47     if (!isroot(y)) ch[z][c] = x;fa[x] = z;
 48     ch[x][!b] = y;fa[y] = x;
 49     ch[y][b] = a;if (a) fa[a] = y;
 50     pushup(y);pushup(x);
 51 }
 52 void splay(int x) {
 53     top = 0;st[++top] = x;
 54     for (int i=x; !isroot(i); i=fa[i]) st[++top] = fa[i];
 55     while (top) pushdown(st[top--]);
 56     while (!isroot(x)) {
 57         int y = fa[x];
 58         if (!isroot(y)) {
 59             if (son(x)==son(y)) rotate(y);
 60             else rotate(x);
 61         }
 62         rotate(x);
 63     }
 64 }
 65 void access(int x) {
 66     for (int t=0; x; t=x,x=fa[x]) {
 67         splay(x);ch[x][1] = t;pushup(x);
 68     }
 69 }
 70 void makeroot(int x) {
 71     access(x);splay(x);rev[x] ^= 1;
 72 }
 73 void link(int x,int y) {
 74     makeroot(x);fa[x] = y;
 75 }
 76 void cut(int x,int y) {
 77     makeroot(x);access(y);splay(y);
 78     ch[y][0] = fa[ch[y][0]] = 0;pushup(y);
 79 }
 80 int find(int x) {
 81     access(x);splay(x);
 82     while (ch[x][0]) x = ch[x][0];
 83     return x;
 84 }
 85 void update(int x,int y,int z) {
 86     makeroot(x);access(y);splay(y);
 87     add[y] += z;mx[y] += z;val[y] += z;
 88 }
 89 int query(int x,int y) {
 90     makeroot(x);access(y);splay(y);
 91     return mx[y];
 92 }
 93 int main() {
 94     while (scanf("%d",&n) != EOF) {
 95         for (int i=0; i<=n; ++i) 
 96             head[i] = add[i] = rev[i] = fa[i] = ch[i][0] = ch[i][1] = 0;
 97         mx[0] = -1e9;tot = 0;
 98         for (int a,b,i=1; i<n; ++i) {
 99             a = read();b = read();
100             add_edge(a,b);add_edge(b,a);
101         }
102         for (int i=1; i<=n; ++i) mx[i] = val[i] = read();
103         st[++top] = 1;
104         for (int k=1; k<=top; ++k) {
105             int u = st[k];
106             for (int i=head[u]; i; i=e[i].nxt) {
107                 int v = e[i].to;
108                 if (v != fa[u]) {
109                     fa[v] = u;st[++top] = v;
110                 }
111             }
112         }
113         m = read();
114         while (m--) {
115             int opt = read(),x = read(),y = read(),w;
116             if (opt==1) {
117                 if (find(x) == find(y)) puts("-1");
118                 else link(x,y);
119             }
120             else if (opt==2) {
121                 if (find(x) != find(y) || x==y) puts("-1");
122                 else cut(x,y);
123             }
124             else if (opt==3) {
125                 w = x;x = y;y = read();
126                 if (find(x) != find(y)) puts("-1");
127                 else update(x,y,w);
128             }
129             else {
130                 if (find(x) != find(y)) puts("-1");
131                 else printf("%d\n",query(x,y));
132             }
133         }
134         puts("");
135     }
136     return 0;
137 }