洛谷 4219/BZOJ 4530 大融合

4530: [Bjoi2014]大融合

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 990 Solved: 604
[Submit][Status][Discuss]

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 <algorithm>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <cstdio>
  6 
  7 inline void read(int & x)
  8 {
  9     int k = 1; x = 0;
 10     char c = getchar();
 11     while (!isdigit(c))
 12         if (c == '-') c = getchar(), k = -1;
 13         else c = getchar();
 14     while (isdigit(c))
 15         x = (x << 1) + (x << 3) + (c ^ 48),
 16         c = getchar();
 17     x *= k;
 18 }
 19 
 20 const int N = 102000;
 21 int n, m, tot, x, y, stk_top;
 22 int faz[N], siz[N], tag[N], son[N][2], stk[N], bson[N];
 23 
 24 char opt;
 25 
 26 inline int Root(int u)
 27 {
 28     return son[faz[u]][1] != u && son[faz[u]][0] != u;
 29 }
 30 
 31 inline char Getchar(void)
 32 {
 33     opt = getchar();
 34     while (opt == ' ' || opt == '
') 
 35         opt = getchar(); 
 36     return opt;
 37 }
 38 
 39 void Swap(int & x, int & y)
 40 {
 41     x ^= y, y ^= x, x ^= y;
 42 }
 43 
 44 inline int Getson(int u)
 45 {
 46     return son[faz[u]][1] == u;
 47 }
 48 
 49 inline void Pushup(int u)
 50 {
 51     if (!u) return;
 52     siz[u] = siz[son[u][0]] + siz[son[u][1]] + bson[u] + 1;
 53 }
 54 
 55 inline void Pushdown(int u)
 56 {
 57     if (!tag[u] || !u) return;
 58     tag[son[u][0]] ^= 1,
 59     tag[son[u][1]] ^= 1,
 60     Swap(son[u][0], son[u][1]),
 61     tag[u] = 0;
 62 }
 63 
 64 inline void Rotate(int u)
 65 {
 66     int y = faz[u], z = faz[y], ch = Getson(u), b = son[u][ch ^ 1];
 67     Pushdown(y), Pushdown(u);
 68     if (!Root(y)) son[z][Getson(y)] = u;
 69     son[u][ch ^ 1] = y, son[y][ch] = b;
 70     faz[u] = z, faz[b] = y, faz[y] = u;
 71     Pushup(y), Pushup(u);
 72 }
 73 
 74 inline void Splay(int u)
 75 {
 76     int cur = u; stk[stk_top = 1] = u;
 77     while (!Root(cur)) stk[++stk_top] = cur = faz[cur];
 78     while (stk_top) Pushdown(stk[stk_top--]);
 79     while (!Root(u))
 80     {
 81         if (!Root(faz[u]))
 82             if (Getson(u) == Getson(faz[u])) Rotate(faz[u]);
 83             else Rotate(u);
 84         Rotate(u);
 85     }
 86 }
 87 
 88 inline void Access(int u)
 89 {
 90     for (int ch = 0; u; u = faz[ch = u])
 91         Splay(u), bson[u] += siz[son[u][1]] - siz[ch], son[u][1] = ch, Pushup(u);
 92 }
 93 
 94 inline void Mkrt(int u)
 95 {
 96     Access(u), Splay(u), tag[u] ^= 1;
 97 }
 98 
 99 inline void Split(int a, int b)
100 {
101     Mkrt(a), Access(b), Splay(b);
102 }
103 
104 inline void Link(int a, int b)
105 {
106     Mkrt(a), Mkrt(b);
107     faz[a] = b, bson[b] += siz[a], Pushup(b);
108 }
109 
110 inline void Get(int a, int b)
111 {
112     Mkrt(a), Mkrt(b);
113     printf("%lld
", (long long)siz[a] * (siz[b] - siz[a]));
114 }
115 
116 int main()
117 {
118     read(n), read(m);
119     for (int i = 1; i <= n; ++i) siz[i] = 1;
120     for (int i = 1; i <= m; ++i)
121     {
122         opt = Getchar(), read(x), read(y);
123         if (opt == 'Q') Get(x, y);
124         if (opt == 'A') Link(x, y);
125     }
126     return 0;
127 }