Feb 17, 2025
HLD
Problem: https://naq23.kattis.com/contests/naq23-fall/problems/veryimportantedge
#include <bits/stdc++.h>
int N, M;
std::vector<std::pair<int, std::pair<int, int>>> edges;
std::vector<std::pair<int, int>> tedges[110000];
std::vector<std::pair<int, std::pair<int, int>>> queries;
int f[110000][20], val[110000], h[110000], size[110000];
int order[110000], order_s, ptr[110000], chain[110000];
std::vector<std::pair<int, int>> ins[110000];
int diff = 0;
int ufs[110000];
int find(int x) {
if (ufs[x] == x)
return x;
return ufs[x] = find(ufs[x]);
}
void merge(int x, int y) {
x = find(x);
y = find(y);
ufs[x] = y;
}
void dfs(int x, int xf, int xval, int xh) {
f[x][0] = xf;
val[x] = xval;
h[x] = xh;
size[x] = 1;
for (auto it : tedges[x])
if (it.first != xf) {
dfs(it.first, x, it.second, xh + 1);
size[x] += size[it.first];
}
}
void dfs3(int x, int xf, int cs) {
ptr[x] = order_s;
order[order_s++] = x;
chain[x] = cs;
int max_son = -1;
for (auto it : tedges[x])
if (it.first != xf) {
if (max_son == -1 || size[max_son] < size[it.first])
max_son = it.first;
}
if (max_son != -1)
dfs3(max_son, x, cs);
for (auto it : tedges[x])
if (it.first != xf && it.first != max_son) {
dfs3(it.first, x, it.first);
}
}
int climb(int x, int dh) {
for (int i = 0; i < 20; ++i)
if (dh & 1 << i)
x = f[x][i];
return x;
}
int lca(int x, int y) {
if (h[x] > h[y])
x = climb(x, h[x] - h[y]);
else
y = climb(y, h[y] - h[x]);
if (x == y)
return x;
for (int i = 19; i >= 0; --i)
if (f[x][i] != f[y][i])
x = f[x][i], y = f[y][i];
return f[x][0];
}
void insert(int a, int b, int v) {
while (h[chain[b]] > h[a]) {
ins[chain[b]].push_back({-v, b});
}
if (h[b] > h[a]) {
ins[climb(b, h[b] - h[a] - 1)].push_back({-v, b});
}
}
int main() {
scanf("%d%d", &N, &M);
for (int i = 0; i < M; ++i) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
edges.push_back({c, {a, b}});
}
std::sort(edges.begin(), edges.end());
for (int i = 1; i <= N; ++i)
ufs[i] = i;
long long ans = 0;
for (int i = 0; i < edges.size(); ++i) {
int c = edges[i].first, a = edges[i].second.first,
b = edges[i].second.second;
if (find(a) != find(b)) {
merge(a, b);
tedges[a].push_back({b, c});
tedges[b].push_back({a, c});
ans += c;
} else {
queries.push_back({c, {a, b}});
}
}
dfs(1, 1, 0, 1);
for (int i = 1; i < 20; ++i)
for (int j = 1; j <= N; ++j)
f[j][i] = f[f[j][i - 1]][i - 1];
dfs3(1, 1, 1);
for (auto it : queries) {
int a = it.second.first, b = it.second.second, l = lca(a, b);
insert(l, a, it.first);
insert(l, b, it.first);
}
std::priority_queue<std::pair<int, int>> s;
for (int _i = 0; _i < order_s; ++_i) {
int i = order[_i];
for (auto j : ins[i])
s.push(j);
while (!s.empty() && ptr[s.top().second] < _i)
s.pop();
if (!s.empty() && i != 1)
diff = std::max(diff, -s.top().first - val[i]);
}
printf("%lld\n", ans + diff);
}