b487. 變態史考古 錯誤報導篇

contents

  1. 1. Problem
    1. 1.1. 題目描述
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

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}$

不幸地,在新聞報導時會因為口誤而傳錯消息,例如在一開始報導 A 的祖先為 R,過了不久受到指責才修正回 A 的祖先為 Q,錯誤報導的氾濫使得程序檢驗要求有效率且有彈性。不少變態因為錯誤報導而造受批判波及,現在要求你協助檢驗受災程度,好讓那些變態向新聞組織申請賠償。

Sample Input

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

Sample Output

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

Solution

相對於 Zerojudge b486. 變態史考古 的動態版本,因此沒辦法離線處理,當然也許有更高招的對操作二分等方式。

用 Link/Cut Tree 這一類的動態樹結構來說,維護有向樹根資訊就相當簡單,接著就是利用 Link/Cut Tree 找 LCA(x, y),先藉由 access(y), splay(y) 將 y 轉到樹根,再把 x 打通到樹根去,最後一個從虛邊接上樹根所在的 splay tree 上的就是 LCA(x, y)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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] = v;
v = u;
v->pushup();
}
return LCA;
}

由於是有根樹,找路徑權重時要防止上下關係發生變化,因此呼叫 void mk_root(Node *u) 操作時,限定 u 一定要是樹根才行。找路徑權重的方式也類似找 LCA 的方法。

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
192
#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.cut(A[x]);
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;
}