G

 avatar
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