Submission

[PPPPPxSSSS]

Score: 0

User: SaccharomycesCerevisiae

Problemset: รัฐบาล

Language: cpp

Time: 0.002 second

Submitted On: 2025-04-16 22:16:49

#include<bits/stdc++.h>
#define pii pair<long long,pair<long long,long long>>
using namespace std;
priority_queue<pii,vector<pii>,greater<pii>>pq;
vector<pii>vec;long long sz[200],hv[200],disc[200],par[200],dep[200],head[200];long long timer = 0;
long long pa[200];long long mem[200];long long aa[200];long long n,m;
vector<pair<long long,long long>>adj[200];
struct SegmentTree{
    long long t[200];
    void build(long long l,long long r,long long i){
        if(l==r){t[i]=aa[l];return;}
        long long m = (l+r)/2;
        build(l,m,i*2);
        build(m+1,r,i*2+1);
        t[i]=max(t[2*i],t[2*i+1]);
        return;
    }
    long long query(long long l,long long r,long long i,long long x,long long y){
        if(l>y||r<x)return LLONG_MIN;
        if(l>=x&&r<=y){
            return t[i];
        }
        long long m = (l+r)/2;
        return max(query(l,m,i*2,x,y),query(m+1,r,i*2+1,x,y));
    }
}f;
long long findpa(long long a){
    if(a==pa[a])return a;
return pa[a]=findpa(pa[a]);
}
void dfs(long long u){
   sz[u]=1;
    for(auto [v,w]:adj[u]){
        if(v==par[u])continue;
        par[v]=u;
        dep[v]=dep[u]+1;
        dfs(v);
        sz[u]+=sz[v];
        if(sz[v]>sz[hv[u]]){mem[v]=w;hv[u]=v;}
    }
    return;
}
void hld(long long u,long long w){
    disc[u]=++timer;
    aa[timer]=w;
    if(head[u]==0)head[u]=u;
    if(hv[u]){
        head[hv[u]]=head[u];
        hld(hv[u],mem[hv[u]]);
    }
    for(auto [v,w]:adj[u]){
         if(v==hv[u])continue;
         if(v==par[u])continue;
         hld(v,w);
    }

return;
}
long long find_path(long long u,long long v){
    vector<pair<long long,long long>>res;long long anss = 0;
    while(head[u]!=head[v]){
        if(dep[head[u]]<dep[head[v]])swap(u,v);
        if(head[u]==u){
            anss=max(anss,f.query(1,n,1,disc[head[u]],disc[u]));
        }
        else anss=max(anss,f.query(1,n,1,disc[head[u]]+1,disc[u]));
        //cout<<head[u]<<" "<<u<<"\n";
        u=par[head[u]];
    }
    if(dep[u]>dep[v])swap(u,v);
    //cout<<u<<" "<<v<<"\n";
    if(u==v)anss = max(anss,f.query(1,n,1,disc[u],disc[v]));
    else anss = max(anss,f.query(1,n,1,disc[u]+1,disc[v]));
    //cout<<"("<<anss<<")";
return anss;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);//Bro made it n*m+m but I prefer n(logn)^2+m :>
    cin>>n>>m;
    for(long long i=0;i<n;i++){
        pa[i+1]=i+1;
    }
    for(long long i=0;i<m;i++){
        long long u,v,w;cin>>u>>v>>w;
        pq.push({w,{u,v}});
    }
    long long ans = 0,ans2=LLONG_MAX;
    while(!pq.empty()){
        auto [w,uu]=pq.top();
        pq.pop();
        auto [u,v]=uu;
        if(findpa(u)==findpa(v)){
            vec.push_back({w,uu});continue;
        }
        pa[findpa(u)]=findpa(v);
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
        ans+=w;
    }

    dfs(1);
    hld(1,0);f.build(1,n,1);
    for(auto [w,uu]:vec){
        //cout<<"["<<uu.first<<" "<<uu.second<<"]\n";
        long long aaa = find_path(uu.first,uu.second);
    //cout<<"---------------\n";
        ans2 = min(ans2,ans-aaa+w);
    }
    cout<<ans<<" "<<ans2;

    return 0;
}