「LG5236」[模板]静态仙人掌(圆方树)

Description

这是一道静态仙人掌(圆方树)的模板题。
如果您不知道什么是仙人掌,那么此处给出无向仙人掌图的定义:

任意一条边至多只出现在一条简单回路的无向连通图称为仙人掌。

给你一个有nn个点和mm条边的仙人掌图,和qq组询问
每次询问两个点u,vu,v,求两点之间的最短路。

Input

第一行三个正整数n,m,qn,m,q,意义如题目描述。
接下来mm行,每行三个正整数u,v,wu,v,w,表示u,vu,v之间有一条权值为ww的无向边。
然后qq行,每行两个正整数u,vu,v,询问uuvv的最短路。

Output

qq行,每行一个正整数,对应一次询问的结果。

Sample Input

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

Sample Output

1
2
5
6

HINT

样例1解释:
样例1中的仙人掌是这个样子的:

询问有两个,分别是询问191\rightarrow 9575\rightarrow 7的最短路

显然答案分别为5566


数据范围
1n,q100001\le n,q \le 10000
1m200001\le m \le 20000
1w1091\le w \le 10^9
请注意时限为300ms300\text{ms}

Solution

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 12000*3, M = 30000*3*2;
int tot;
int n, m, Q;
int sum[N];
struct G2 {
struct Edge {
int u, v, nxt, w;
}e[M];
int head[N], en;
void addedge(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
e[en].w = z;
// printf("%d->%d\n", x, y);
}
int son[N], siz[N], dis[N];
int fa[N], d[N];
void dfs1(int x, int F) {
siz[x] =1;
fa[x] = F;
d[x] = d[F] + 1;
for(int i = head[x]; i;i = e[i].nxt) {
int y = e[i].v;
if(y == F) continue;
dis[y] = dis[x] + e[i].w;
dfs1(y, x);
siz[x] += siz[y];
if(siz[son[x]] < siz[y]) son[x] = y;
}
}
int id[N], num, top[N];
void dfs2(int x, int F) {
id[x] = ++num;
top[x] = F;
if(!son[x]) return;
dfs2(son[x], F);
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].v;
if(y == fa[x] || y == son[x]) continue;
dfs2(y, y);
}
}
int lca(int x, int y) {
/* if(d[x] > d[y]) swap(x, y);
while(top[y] != top[x]) {
y = fa[top[y]];
}
if(d[x] > d[y]) swap(x, y);*/
//return son[x];
while(top[x] != top[y]) {
if(d[top[x]] > d[top[y]]) swap(x, y);
y = fa[top[y]];
}
return d[x] < d[y] ? x : y;
}
int find(int x, int f) {
int res = x;
while(top[x] != top[f]) {
res = top[x];
x = fa[top[x]];
}
return x == f ? res : son[f];
}
void solve() {
for(int i = 1; i <= Q; ++i) {
int x = read(), y = read();
int z = lca(x, y);
if(z <= n) writeln(dis[x] + dis[y] - 2 * dis[z]);
else {
int a = find(x, z);
int b = find(y, z);
int ans = abs(sum[a] - sum[b]);
ans = min(ans, sum[z] - ans);
ans += dis[x] - dis[a] + dis[y] - dis[b];
writeln(ans);
}
}
}
}g2;
struct G1 {
struct Edge {
int u, v, nxt, w;
}e[M];
int head[N], en;
void addedge(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
e[en].w = z;
}
int low[N], num, dfn[N], b[N], fa[N];
void solve(int x, int F, int w) {
int i = x;
++tot;
sum[tot] = w;
while(i != F) {
sum[i] = sum[tot];
sum[tot] += b[i];
i = fa[i];
}
i = x;
while(i != F) {
int val = min(sum[i], sum[tot] - sum[i]);
g2.addedge(tot, i, val);
g2.addedge(i, tot, val);
i = fa[i];
}
g2.addedge(F, tot, 0);
g2.addedge(tot, F, 0);
}
void tarjan(int x, int in_edge) {
low[x] = dfn[x] = ++num;
for(int i = head[x]; i;i = e[i].nxt) if(i != (in_edge ^ 1)){
int y = e[i].v;
if(!dfn[y]) {
b[y] = e[i].w;
fa[y] = x;
tarjan(y, i);
low[x] = min(low[x], low[y]);
} else low[x] = min(low[x], dfn[y]);
if(low[y] <= dfn[x]) continue;
g2.addedge(x, y, e[i].w);
g2.addedge(y, x, e[i].w);
}
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].v;
//if(low[y] != dfn[x] || fa[y] == x) continue;
if(dfn[y] <= dfn[x] || fa[y] == x) continue;
solve(y, x, e[i].w);
}
}
}g1;
int main() {
g1.en = 1;
n = read(), m = read(), Q = read();
tot = n;
for(int i = 1; i <= m; ++i) {
int x = read(), y = read(), z = read();
g1.addedge(x, y, z);
g1.addedge(y, x, z);
}
g1.tarjan(1, 0);
g2.dfs1(1, 0);
g2.dfs2(1, 1);
g2.solve();
return 0;
}