b486. 變態史考古

contents

  1. 1. Problem
    1. 1.1. 題目描述
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution
    1. 4.1. 離線處理 + 倍增算法
    2. 4.2. LCT

Problem

題目描述

隨著考古學者近幾年的研究,逐漸地分析出變態人類文化族群的祖先。同時也知道,每一代人會將其變態基因傳遞給下一代,而下一代的變態指數會比上一代多一。若子代有數個,每個子代帶有的變態性向會有所歧異。

每當新聞報導某個變態父子關係時,人們總會熱議某兩個變態的相似程度。口耳相傳的消息是不可信任的,現在給予事情發生的時間軸,請驗證人們口中的變態相似程度。

變態相似程度定義

$\textit{sim}(A, B) = \frac{\textit{dist}(\textit{Original}(A), \textit{LCA}(A, B)) \times 2}{\textit{dist}(\textit{Original}(A), A) + \textit{dist}(\textit{Original}(B), B)}$

其中 $\textit{Original}(A)$ 表示根據事實推測得到的最早源頭祖先,$\textit{dist}(A, B)$ 表示在樹狀圖中兩點的距離,$\textit{LCA}(A, B)$ 表示 $A, \; B$ 最小公共祖先 (Lowest Common Ancestor,簡稱 LCA)。

例如當前知道的祖先關係如下

1
2
3
4
5
6
7
P
/
Q
/ \
A R
/
B
  • $\textit{Original}(A) = \textit{Original}(B) = P$
  • $\textit{dist}(P, A) = 3, \; \textit{dist}(P, B) = 4, \; \textit{LCA}(A, B) = Q, \; \textit{dist}(Q, P) = 2$
  • 最後 $\textit{sim}(A, B) = \frac{4}{7}$

Sample Input

1
2
3
4
5
6
7
8
9
10
5 9
news 3 2
news 4 2
sim 3 4
sim 3 5
news 2 1
news 5 4
sim 3 4
sim 3 5
sim 4 4

Sample Output

1
2
3
4
5
1/2
-1
2/3
4/7
1/1

Solution

維護一個有根森林的建造,在建造過程中找尋 LCA。出這一題時,測資只有打算卡暴力解,意即使用慢慢往上爬找交會的算法。預計會有很多種解法,因為建樹結果是唯一的,於是柳州 101 果真給我一個離線的方案。

使用離線處理把建樹的資訊保留,利用倍增算法找攀升的祖先,隨後模擬時,使用並查集維護當前所在樹的樹根,由於要找到 LCA 到當前樹根的距離,其實就相當於找到最終樹根的距離去扣除即可。

另外的解法是採用 Link/Cut Tree,直接套模板找 LCA 就相當簡單。

離線處理 + 倍增算法

倍增算法實作時特別小心快取置換,例如陣列宣告 arr[MAXLOGN][MAXN]arr[MAXN][MAXLOGN] 使用 dp 建表時,前者速度會比後者快上三倍之多 (當 MAXN = 200000 以上)。

但是在找 LCA 時,access memory 又會變慢,所以見仁見智。若是在 RMQ 的 sparse table 處理上會有很大的影響。

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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXLOGN = 17;
struct Event {
char s[8];
int x, y;
void read() {
scanf("%s %d %d", s, &x, &y);
}
};
int fa[MAXLOGN][MAXN], visited[MAXN], dep[MAXN];
int parent[MAXN];
vector<int> g[MAXN];
void dfs(int u) {
visited[u] = 1;
for (auto v : g[u]) {
fa[0][v] = u;
dep[v] = dep[u] + 1;
dfs(v);
}
}
int findp(int x) {
return x == parent[x] ? x : (parent[x]=findp(parent[x]));
}
int LCA(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
int d = dep[x] - dep[y];
for (int i = MAXLOGN-1; i >= 0; i--) {
if ((d>>i)&1) {
d -= 1<<i;
x = fa[i][x];
}
}
if (x == y) return x;
for (int i = MAXLOGN-1; i >= 0; i--) {
if (fa[i][x] != fa[i][y]) {
x = fa[i][x], y = fa[i][y];
}
}
return fa[0][x];
}
void sim(int x, int y) {
int rx, ry, lca;
rx = findp(x), ry = findp(y);
if (rx != ry) {
puts("-1");
return ;
}
lca = LCA(x, y);
int a = (dep[lca]-dep[rx]+1)*2, b = dep[x]+dep[y]-dep[rx]*2+2, g;
g = __gcd(a, b), a /= g, b /= g;
printf("%d/%d\n", a, b);
}
int main() {
int n, m;
while (scanf("%d %d", &n, &m) == 2) {
for (int i = 1; i <= n; i++)
g[i].clear(), visited[i] = 0, parent[i] = i;
vector<Event> e(m);
for (int i = 0; i < m; i++) {
e[i].read();
if (e[i].s[0] == 'n')
g[e[i].y].push_back(e[i].x);
}
memset(visited, 0, (n+1) * sizeof(visited[0]));
for (int i = 1; i <= n; i++) {
if (visited[i] == 0)
dfs(i);
}
for (int i = 1; i < MAXLOGN; i++)
for (int j = 1; j <= n; j++)
fa[i][j] = fa[i-1][fa[i-1][j]];
for (int i = 0; i < m; i++) {
if (e[i].s[0] == 'n') {
parent[e[i].x] = e[i].y;
} else {
sim(e[i].x, e[i].y);
}
}
}
return 0;
}

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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
#include <bits/stdc++.h>
using namespace std;
class LCT { // Link-Cut Tree
public:
static const int MAXN = 100005;
struct Node {
static Node *EMPTY;
Node *ch[2], *fa;
int rev;
int size;
Node() {
ch[0] = ch[1] = fa = NULL;
rev = 0;
size = 1;
}
bool is_root() {
return fa->ch[0] != this && fa->ch[1] != this;
}
void pushdown() {
if (rev) {
ch[0]->rev ^= 1, ch[1]->rev ^= 1;
swap(ch[0], ch[1]);
rev ^= 1;
}
}
void pushup() {
if (this == EMPTY) return ;
size = 1;
if (ch[0] != EMPTY)
size += ch[0]->size;
if (ch[1] != EMPTY)
size += ch[1]->size;
}
} _mem[MAXN];
int bufIdx;
LCT() {
Node::EMPTY = &_mem[0];
Node::EMPTY->fa = Node::EMPTY->ch[0] = Node::EMPTY->ch[1] = Node::EMPTY;
Node::EMPTY->size = 0;
bufIdx = 1;
}
void init() {
bufIdx = 1;
}
Node* newNode() {
Node *u = &_mem[bufIdx++];
*u = Node();
u->fa = u->ch[0] = u->ch[1] = Node::EMPTY;
return u;
}
void rotate(Node *x) {
Node *y;
int d;
y = x->fa, d = y->ch[1] == x ? 1 : 0;
x->ch[d^1]->fa = y, y->ch[d] = x->ch[d^1];
x->ch[d^1] = y;
if (!y->is_root())
y->fa->ch[y->fa->ch[1] == y] = x;
x->fa = y->fa, y->fa = x;
y->pushup(), x->pushup();
}
void deal(Node *x) {
if (!x->is_root()) deal(x->fa);
x->pushdown();
}
void splay(Node *x) {
Node *y, *z;
deal(x);
while (!x->is_root()) {
y = x->fa, z = y->fa;
if (!y->is_root()) {
if (y->ch[0] == x ^ z->ch[0] == y)
rotate(x);
else
rotate(y);
}
rotate(x);
}
x->pushup();
}
Node* access(Node *u) {
Node *v = Node::EMPTY;
for (; u != Node::EMPTY; u = u->fa) {
splay(u);
u->ch[1] = v;
v = u;
v->pushup();
}
return v;
}
void mk_root(Node *u) {
access(u)->rev ^= 1, splay(u);
}
void cut(Node *x, Node *y) {
mk_root(x);
access(y), splay(y);
y->ch[0] = x->fa = Node::EMPTY;
}
Node* cut(Node *x) {
Node *u, *v, *rt = find(x);
mk_root(rt);
access(x), splay(x);
for (v = x->ch[0]; v->ch[1] != Node::EMPTY; v = v->ch[1]);
x->ch[0]->fa = x->fa;
x->fa = x->ch[0] = Node::EMPTY;
return v;
}
void link(Node *x, Node *y) {
mk_root(x);
x->fa = y;
}
Node* find(Node *x) {
for (x = access(x); x->pushdown(), x->ch[0] != Node::EMPTY; x = x->ch[0]);
return x;
}
//
Node* lca(Node *x, Node *y) {
if (x == y) return x;
if (find(x) != find(y))
return Node::EMPTY;
Node *u, *v = Node::EMPTY, *LCA = Node::EMPTY;
access(y), splay(y);
for (u = x; u != Node::EMPTY; u = u->fa) {
splay(u);
if (u->fa == Node::EMPTY) {
LCA = u;
// u->ch[1]->push_add(c), v->push_add(c);
}
u->ch[1] = v;
v = u;
v->pushup();
}
return LCA;
}
int path(Node *x, Node *y) {
int ret;
Node *u, *v = Node::EMPTY;
access(y), splay(y);
for (u = x; u != Node::EMPTY; u = u->fa) {
splay(u), u->pushdown();
if (u->fa == Node::EMPTY) {
ret = u->ch[1]->size + v->size;
}
u->ch[1] = v;
v = u;
v->pushup();
}
return ret;
}
inline int label(Node *x) {
return x - _mem;
}
} tree;
LCT::Node *LCT::Node::EMPTY;
LCT::Node *A[100005], *node_x, *node_rt;
int main() {
int n, m, x, y, c, u, v;
char cmd[8];
while (scanf("%d %d", &n, &m) == 2) {
tree.init();
for (int i = 1; i <= n; i++)
A[i] = tree.newNode();
for (int i = 0; i < m; i++) {
scanf("%s", cmd);
if (cmd[0] == 'n') { // link
scanf("%d %d", &x, &y);
tree.link(A[x], A[y]);
} else if (cmd[0] == 's') { // sim
scanf("%d %d", &x, &y);
node_x = tree.lca(A[x], A[y]);
int lca = tree.label(node_x);
if (lca == 0) {
puts("-1");
} else {
node_rt = tree.find(A[lca]);
int p1, p2;
p1 = tree.path(A[x], A[y]) + 1;
p2 = tree.path(A[lca], node_rt) + 1;
int a = p2*2, b = p1 + p2*2 - 1, g;
g = __gcd(a, b), a /= g, b /= g;
printf("%d/%d\n", a, b);
}
}
}
}
return 0;
}