#include using namespace std; #define int long long struct edge{int u, v, w, i;}; const int MX = 2e5+2, MXLG = 19; int par[MX], spw[MXLG][MX], spw2[MXLG][MX], spp[MXLG][MX], height[MX]; vector> adj[MX]; vector edges; bool used[MX]; int f(int i){return i==par[i]?i:par[i]=f(par[i]);} void dfs(int i, int p, int h) { height[i] = h; for(auto [v, w]: adj[i]) { if(v == p) continue; spw[0][v] = w; spw2[0][v] = -1; spp[0][v] = i; dfs(v, i, h+1); } } void mx2(vector v, int& m1, int& m2) { assert(v.size() >= 2); sort(v.begin(), v.end(), greater()); unique(v.begin(), v.end()); m1 = v[0]; m2 = v[1]; } int32_t main() { ios::sync_with_stdio(0);cin.tie(0); int n, m; cin >> n >> m; for(int i=0; i> u >> v >> w; edges.push_back({u, v, w, i}); } for(int i=1; i<=n; i++) par[i] = i; sort(edges.begin(), edges.end(), [](edge a, edge b){return a.w < b.w;}); int curw = 0; for(int i=0; i=0; i--) { if(spp[i][u] != spp[i][v]) { mx2({m1, m2, spw[i][v], spw2[i][v], spw[i][u], spw2[i][u]}, m1, m2); u = spp[i][u]; v = spp[i][v]; } } if(u != v) { mx2({m1, m2, spw[0][u], spw[0][v]}, m1, m2); } //printf("for edge of u, v, w=%lld, %lld, %lld, m1=%lld, m2=%lld\n", e.u, e.v, w, m1, m2); cout << curw + (w - m1) << '\n'; } }

코드 #4211