-
Notifications
You must be signed in to change notification settings - Fork 11
Expand file tree
/
Copy pathDISQUERY.cpp
More file actions
117 lines (117 loc) · 3.29 KB
/
Copy pathDISQUERY.cpp
File metadata and controls
117 lines (117 loc) · 3.29 KB
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
// Ivan Carvalho
// Solution to https://www.spoj.com/problems/DISQUERY/
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <vector>
#define MAXN 100010
#define MP make_pair
using namespace std;
typedef pair<int, int> ii;
vector<ii> grafo[MAXN];
int pai[MAXN], superpai[MAXN], nivel[MAXN], estrela[MAXN], segmento, n;
ii ligapai[MAXN], ligasuperpai[MAXN];
void dfs_pai(int x) {
for (int i = 0; i < grafo[x].size(); i++) {
int v = grafo[x][i].first;
if (pai[v] == -1) {
pai[v] = x;
ligapai[v] = MP(grafo[x][i].second, grafo[x][i].second);
nivel[v] = nivel[x] + 1;
dfs_pai(v);
}
}
}
void dfs_superpai(int x, int p) {
superpai[x] = p;
if (nivel[x] % segmento == 0) {
p = x;
estrela[x] = 1;
}
for (int i = 0; i < grafo[x].size(); i++) {
int v = grafo[x][i].first;
if (superpai[v] == -1) {
dfs_superpai(v, p);
}
}
}
ii LCA(int u, int v) {
int maior = -1, menor = 1e9 + 1;
while (superpai[u] != superpai[v]) {
if (nivel[u] > nivel[v]) {
if (!estrela[u]) {
menor = min(ligapai[u].first, menor);
maior = max(ligapai[u].second, maior);
u = pai[u];
} else {
menor = min(ligasuperpai[u].first, menor);
maior = max(ligasuperpai[u].second, maior);
u = superpai[u];
}
} else {
if (!estrela[v]) {
menor = min(ligapai[v].first, menor);
maior = max(ligapai[v].second, maior);
v = pai[v];
} else {
menor = min(ligasuperpai[v].first, menor);
maior = max(ligasuperpai[v].second, maior);
v = superpai[v];
}
}
}
while (u != v) {
if (nivel[u] > nivel[v]) {
menor = min(ligapai[u].first, menor);
maior = max(ligapai[u].second, maior);
u = pai[u];
} else {
menor = min(ligapai[v].first, menor);
maior = max(ligapai[v].second, maior);
v = pai[v];
}
}
return MP(menor, maior);
}
int main() {
scanf("%d", &n);
segmento = 1;
for (int i = 1; i <= n; i++) {
pai[i] = superpai[i] = -1;
}
for (int i = 1; i < n; i++) {
int u, v, peso;
scanf("%d %d %d", &u, &v, &peso);
grafo[u].push_back(MP(v, peso));
grafo[v].push_back(MP(u, peso));
}
nivel[1] = 0;
pai[1] = 1;
superpai[1] = 1;
ligapai[1] = MP(1000000001, -1);
dfs_pai(1);
for (int i = 1; i <= n; i++) segmento = max(segmento, nivel[i]);
segmento = sqrt(segmento);
dfs_superpai(1, 1);
for (int i = 1; i <= n; i++) {
if (!estrela[i]) continue;
int alvo = superpai[i];
int menor = 1e9 + 1, maior = -1;
int temp = i;
while (temp != alvo) {
menor = min(ligapai[temp].first, menor);
maior = max(ligapai[temp].second, maior);
temp = pai[temp];
}
ligasuperpai[i] = MP(menor, maior);
}
int q;
scanf("%d", &q);
while (q--) {
int u, v, peso;
scanf("%d %d", &u, &v);
ii resp = LCA(u, v);
printf("%d %d\n", resp.first, resp.second);
}
return 0;
}