#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define vpii vector<pii>
#define vi vector<int>
int N, M;
int cnt = 0;
int anc[100000][17];
int depth[100000];
int mx[100000][17];
int in[100000];
int out[100000];
vpii adj[100000];
vpii mst[100000];
struct Edge { int u, v, d; } E[300000];
int dsu[100000];
int find(int a) { return dsu[a] = a == dsu[a] ? a : find(dsu[a]); }
void merge(int a, int b) { a = find(a); b = find(b); dsu[a] = b; }
bool cmp1(int i, int j) { return in[i] < in[j]; }
bool cmp2(Edge a, Edge b) { return a.d < b.d; }
void dfs(int n) {
in[n] = cnt++;
for (auto [m, d]: mst[n]) {
if (anc[n][0] == m) continue;
anc[m][0] = n;
mx[m][0] = d;
depth[m] = depth[n] + 1;
dfs(m);
}
out[n] = cnt;
}
void initLCA() {
for (int i = 1; i < 17; i++) {
for (int n = 0; n < N; n++) {
if (anc[n][i-1] == -1) continue;
anc[n][i] = anc[anc[n][i-1]][i-1];
mx[n][i] = max(mx[n][i-1], mx[anc[n][i-1]][i-1]);
}
}
}
int LCA(int a, int b) {
if (depth[a] > depth[b]) swap(a, b);
for (int i = 16; i >= 0; i--) {
if (depth[b]-depth[a] >= (1<<i)) b = anc[b][i];
}
if (a == b) return a;
for (int i = 16; i >= 0; i--) {
if (anc[a][i] != anc[b][i]) a = anc[a][i], b = anc[b][i];
}
return anc[a][0];
}
int getMx(int a, int b) {
int ret = 0;
if (depth[a] > depth[b]) swap(a, b);
for (int i = 16; i >= 0; i--) {
if (depth[b]-depth[a] >= (1<<i)) {
ret = max(ret, mx[b][i]);
b = anc[b][i];
}
}
if (a == b) return ret;
for (int i = 16; i >= 0; i--) {
if (anc[a][i] != anc[b][i]) {
a = anc[a][i], b = anc[b][i];
ret = max(ret, max(mx[a][i], mx[b][i]));
}
}
ret = max(ret, max(mx[a][0], mx[b][0]));
return ret;
}
ll kruskal() {
ll ret = 0;
sort(E, E+M, cmp2);
for (int n = 0; n < N; n++) dsu[n] = n;
for (int m = 0; m < M; m++) {
auto [u, v, d] = E[m];
if (find(u) == find(v)) continue;
merge(u, v);
ret += d;
mst[u].push_back({ v, d });
mst[v].push_back({ u, d });
}
return ret;
}
vpii tadj[100000];
bool flag[100000];
bool isanc(int a, int b) { return in[a] <= in[b] && in[b] <= out[a]; }
ll dp(int n, int s, int p) {
ll ret = 0;
for (auto [m, w]: tadj[n]) {
if (m == p) continue;
if (s == 0) ret += dp(m, flag[m], n);
else {
if (flag[m]) ret += w + dp(m, 1, n);
else ret += max(w + dp(m, 0, n), dp(m, 1, n));
}
}
return ret;
}
ll solve(int n) {
vi v = { n }; flag[n] = 1;
for (auto [m, w]: adj[n]) { v.push_back(m); flag[m] = 1; }
sort(v.begin(), v.end(), cmp1);
int tmp = v.size();
for (int i = 0; i < tmp-1; i++) v.push_back(LCA(v[i], v[i+1]));
sort(v.begin(), v.end(), cmp1);
v.erase(unique(v.begin(), v.end()), v.end());
for (int m: v) tadj[m] = {};
stack<int> st;
for (int m: v) {
while (st.size() && !isanc(st.top(), m)) {
int a = st.top(); st.pop();
int d = getMx(a, st.top());
tadj[st.top()].push_back({ a, d });
tadj[a].push_back({ st.top(), d });
}
st.push(m);
}
while (st.size() >= 2) {
int a = st.top(); st.pop();
int d = getMx(a, st.top());
tadj[st.top()].push_back({ a, d });
tadj[a].push_back({ st.top(), d });
}
ll ret = dp(n, 1, -1);
for (int m: v) flag[m] = 0;
return ret;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
memset(anc, -1, sizeof(anc));
memset(mx, 0, sizeof(mx));
memset(flag, 0, sizeof(flag));
cin >> N >> M;
for (int m = 0; m < M; m++) {
int u, v, d; cin >> u >> v >> d; u--; v--;
adj[u].push_back({ v, d });
adj[v].push_back({ u, d });
E[m] = { u, v, d };
}
ll sum = kruskal();
anc[0][0] = -1; depth[0] = 0; dfs(0);
initLCA();
for (int n = 0; n < N; n++) {
ll ans = sum;
for (auto [m, w]: adj[n]) ans += w;
ans -= solve(n);
cout << ans << '\n';
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
14 ms |
20940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
14 ms |
20940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
