bzoj 4530[BJOI2014]大融合

BZOJ4530 [Bjoi2014]大融合

Time Limit: 30 Sec Memory Limit: 512 MB

Description

小强要在N个孤立的星球上建立起一套通信系统。这套通信系统就是连接N个点的一个树。

这个树的边是一条一条添加上去的。在某个时刻，一条边的负载就是它所在的当前能够

联通的树上路过它的简单路径的数量。

例如，在上图中，现在一共有了5条边。其中，(3,8)这条边的负载是6，因

为有六条简单路径2-3-8,2-3-8-7,3-8,3-8-7,4-3-8,4-3-8-7路过了(3,8)。

现在，你的任务就是随着边的添加，动态的回答小强对于某些边的负载的

询问。

Input

第一行包含两个整数N,Q，表示星球的数量和操作的数量。星球从1开始编号。

接下来的Q行，每行是如下两种格式之一：

A x y 表示在x和y之间连一条边。保证之前x和y是不联通的。

Q x y 表示询问(x,y)这条边上的负载。保证x和y之间有一条边。

1≤N,Q≤100000

Output

对每个查询操作，输出被查询的边的负载。

Sample Input

8 6
A 2 3
A 3 4
A 3 8
A 8 7
A 6 5
Q 3 8

Sample Output

这道题是一道用LCT维护虚树大小的板子题

我们只需要单独用一个变量存储虚树大小，当一个节点的一条重链变成轻链时，它的虚树大小就加上断开的子树大小即可，反之减掉即可

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #define LL long long
  6 #define lc t[x].ch[0]
  7 #define rc t[x].ch[1] 
  8 
  9 using namespace std;
 10 
 11 const int MAXN = 1e5 + 10;
 12 
 13 int N, Q;
 14 char opr[10];
 15 
 16 int s[MAXN];
 17 struct node {
 18     int ch[2];
 19     int fa;
 20     int lazy;
 21     int size;
 22     int val; 
 23 } t[MAXN];
 24 
 25 inline LL read()
 26 {
 27     LL x = 0, w = 1; char ch = 0;
 28     while(ch < '0' || ch > '9') {
 29         if(ch == '-') {
 30             w = -1;
 31         }
 32         ch = getchar();
 33     }
 34     while(ch >= '0' && ch <= '9') {
 35         x = x * 10 + ch - '0';
 36         ch = getchar();
 37     }
 38     return x * w;
 39 }
 40 
 41 void pushdown(int x)
 42 {
 43     if(t[x].lazy) {
 44         swap(lc, rc);
 45         t[lc].lazy ^= 1;
 46         t[rc].lazy ^= 1;
 47         t[x].lazy = 0;
 48     }
 49 }
 50 
 51 bool isroot(int x)
 52 {
 53     return t[t[x].fa].ch[0] != x && t[t[x].fa].ch[1] != x;
 54 }
 55 
 56 void pushup(int x)
 57 {
 58     t[x].val = t[x].size + t[lc].val + t[rc].val + 1;
 59 }
 60 
 61 void rotate(int x)
 62 {
 63     int y = t[x].fa, z = t[y].fa;
 64     int l, r;
 65     if(!isroot(y)) {
 66         if(t[z].ch[0] == y) {
 67             t[z].ch[0] = x;
 68         } else {
 69             t[z].ch[1] = x;
 70         }
 71     }
 72     if(t[y].ch[0] == x) {
 73         l = 0;
 74     } else {
 75         l = 1;
 76     }
 77     r = l ^ 1;
 78     t[y].ch[l] = t[x].ch[r], t[t[x].ch[r]].fa = y;
 79     t[x].ch[r] = y, t[x].fa = z, t[y].fa = x;
 80     pushup(y);
 81     pushup(x);
 82 }
 83 
 84 void splay(int x)
 85 {
 86     int y = x;
 87     int cnt = 0;
 88     while(!isroot(y)) {
 89         s[++cnt] = y;
 90         y = t[y].fa;
 91     }
 92     s[++cnt] = y;
 93     while(cnt) {
 94         pushdown(s[cnt--]);
 95     }
 96     while(!isroot(x)) {
 97         int y = t[x].fa, z = t[y].fa;
 98         if(!isroot(y)) {
 99             if((t[y].ch[0] == x) ^ (t[z].ch[0] == y)) {
100                 rotate(x);
101             } else {
102                 rotate(y);
103             }
104         }
105         rotate(x);
106     }
107 }
108 
109 void access(int x)
110 {
111     for(int y = 0; x; y = x, x = t[x].fa) {
112         splay(x);
113         t[x].size += t[rc].val;
114         rc = y;
115         t[x].size -= t[rc].val;
116         pushup(x);
117     }
118 }
119 
120 void makeroot(int x)                                                                 
121 {
122     access(x);
123     splay(x);
124     t[x].lazy ^= 1;
125 }
126 
127 void split(int x, int y)
128 {
129     makeroot(x);
130     access(y);
131     splay(y);
132 }
133 
134 void link(int x, int y)
135 {
136     makeroot(x);
137     //split(x, y);
138     t[x].fa = y;
139     t[y].size += t[x].val;
140     pushup(y);
141 }
142 
143 int findroot(int x)
144 {
145     access(x), splay(x);
146     pushdown(x);
147     while(lc) {
148         x = lc;
149         pushdown(x);
150     }
151     return x;
152 }
153 
154 int main()
155 {
156     N = read(), Q = read(); 
157     for(int i = 1; i <= N; i++) {
158         t[i].val = 1;
159     }
160     for(int i = 1; i <= Q; i++) {
161         scanf("%s", opr);
162         int x = read(), y = read();
163         if(opr[0] == 'A') {
164             link(x, y);
165         } else {
166             split(x, y);
167             LL ans = (t[x].size + 1) * (t[y].size + 1);
168             printf("%lld
", ans);
169         }
170     }
171 }

View Code