G
meda
c_cpp
2 months ago
2.6 kB
15
Indexable
#include<bits/stdc++.h> #define ll long long #define endl "\n" using namespace std; template<class T> void printff(vector<T>& v) { for (auto k : v) cout << k << " "; cout << endl; } struct DSU{ int n; vector<int> parent, size; int components; DSU(int n){ parent = size = vector<int>(n + 1); components = n; for (int i = 1; i <= n; i++){ parent[i] = i; size[i] = 1; } } int find(int v){ return parent[v] = (parent[v] == v ? v : find(parent[v])); } void union_sets(int a, int b){ a = find(a); b = find(b); if (a != b){ if (size[a] < size[b]) swap(a, b); parent[b] = a; size[a] += size[b]; components--; } } }; void SOLVE() { int n, m; cin >> n >> m; vector<tuple<ll, int, int>> edges(m); for(auto &[w, u, v] : edges){ cin >> u >> v >> w; } sort(edges.begin(), edges.end()); DSU t(n + 1); vector<vector<int>> graph(n + 1); ll total = 0; for(auto &[w , u, v] : edges){ if(t.find(u) == t.find(v)) continue; t.union_sets(u, v); graph[u].push_back(v); graph[v].push_back(u); total += w; } vector<int> f(n + 1); function<void(int, int)> dfs =[&] (int node, int parent){ int mx = -1; for(auto child : graph[node]){ if(child == parent) continue; dfs(child, node); mx = max(mx, f[child]); } f[node] = mx + 1; }; dfs(1, - 1); vector<int> g(n + 1); function<void(int, int)> dfs2 =[&] (int node, int parent){ int mx1 = -1, mx2 = -1; for (auto child : graph[node]) { if (child == parent) continue; if (f[child] > mx1) { mx2 = mx1; mx1 = f[child]; } else if (f[child] > mx2) { mx2 = f[child]; } } for (auto child : graph[node]) { if (child == parent) continue; if (f[child] == mx1) { g[child] = max(g[child], mx2 + 2); } else { g[child] = max(g[node], mx1 + 2); } g[child] = max(g[child], g[node] + 1); dfs2(child, node); } }; dfs2(1, -1); int mx = 0; for(int i = 1; i <= n; i++) mx = max({mx, f[i], g[i]}); cout << total << endl << mx << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int tc = 1; //cin >> tc; while(tc--) SOLVE(); return 0; }
Editor is loading...
Leave a Comment