目录

  1. 引言
  2. BZOJ 4530: [Bjoi2014]大融合
    1. Description
    2. Input
    3. Output
    4. Sample Input
    5. Sample Output
    6. Source
    7. 题目分析
    8. 代码

引言

BZOJ 4530: [Bjoi2014]大融合 题解

BZOJ 4530: [Bjoi2014]大融合

  • Time Limit: 10 Sec

  • Memory Limit: 256 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

6

Source

鸣谢佚名上传

题目分析

LCT维护子树信息,当然也可以用离线树链剖分来搞

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <cassert>
//#define TEST
#define maxn 200005
#define ls ch[x][0]
#define rs ch[x][1]
#define ll long long int
#define rep(i, l, r) for (register int i = l; i <= r; i++)
#define per(i, r, l) for (register int i = r; i >= l; i--)
#define gc() ((p1 == p2 && (p2 = (p1 = buffer) + fread(buffer, 1, maxn, stdin), p1 == p2)) ? EOF : *p1++)
using namespace std;
char *p1, *p2;
char buffer[maxn];
template <class T> void read(T& x){
char ch = gc(); x = 0; bool f = 1;
while (!('0' <= ch && ch <= '9') && ch != '-') ch = gc();
if (ch == '-') f = 0, ch = gc();
while ('0' <= ch && ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = gc();
if (!f) x = -x;
}
int n, m;
int siz[maxn];
int vsiz[maxn];
int fa[maxn];
int ch[maxn][2];
bool rev[maxn];
void debug(){
rep(x, 0, n){
printf("#%d : siz = %d, vsiz = %d, ls = %d, rs = %d, fa = %d, rev = %d\n", x, siz[x], vsiz[x], ls, rs, fa[x], rev[x]);
}
printf("\n\n\n");
}
inline bool is_root(int x){
return ch[fa[x]][0] != x && ch[fa[x]][1] != x;
}
inline void pushup(int x){
siz[x] = siz[ls] + siz[rs] + vsiz[x] + 1;
}
inline void pushv(int x, int op){ //op == 1 || op == -1
vsiz[fa[x]] += op * siz[x];
}
inline void pushdown(int x){
if (rev[x]){
rev[ls] ^= 1, rev[rs] ^= 1;
rev[x] = 0;
swap(ls, rs);
}
}
void rotate(int x, int d){
int k = ch[x][d];
fa[k] = fa[x];
if (!is_root(x)) ch[fa[x]][ch[fa[x]][1] == x] = k;
ch[x][d] = ch[k][d ^ 1];
fa[ch[x][d]] = x;
ch[k][d ^ 1] = x;
fa[x] = k;
pushup(x);
pushup(k);
}
stack<int> s;
void splay(int x){
int t = x;
while (!is_root(x)){
s.push(x);
x = fa[x];
}
s.push(x);//Error!!!!
while (!s.empty()){
pushdown(s.top());
s.pop();
}
x = t;
while (!is_root(x)){
int f1 = fa[x];
int d1 = ch[f1][1] == x;
if (!is_root(f1)){
int f2 = fa[f1];
int d2 = ch[f2][1] == f1;
if (d1 ^ d2) rotate(f1, d1), rotate(f2, d2);
else rotate(f2, d2), rotate(f1, d1);
}
else rotate(f1, d1);
}
}
void access(int x){
int t = 0;
while (x){
splay(x);
pushv(rs, 1), pushv(t, -1);
rs = t;
pushup(x);
t = x;
x = fa[x];
}
}
void moveroot(int x){
access(x), splay(x), rev[x] ^= 1;
}
void split(int x, int y){
moveroot(y), access(x), splay(x);
}
void link(int x, int y){
moveroot(x), access(y), splay(y);
fa[x] = y;
pushv(x, 1);
pushup(y);
}
ll get(int x, int y){
split(x, y);
int a = vsiz[x] + 1;
split(y, x);
int b = vsiz[y] + 1;
return (ll) a * b;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("comb.in", "r", stdin);
#ifdef TEST
freopen("comb.out", "w", stdout);
#endif
#endif
int x, y;
read(n), read(m);
char op;
rep(i, 1, m){
op = gc();
while (op != 'Q' && op != 'A') op = gc();
switch(op){
case 'A': read(x), read(y), link(x, y); break;
case 'Q': read(x), read(y), printf("%lld\n", get(x, y)); break;
default: assert(false); break;
}
#ifdef TEST
debug();
#endif
}
return 0;
}