87D - Beautiful Road - CodeForces Solution

/*
    in the name of god
    created by: mohammadsam
*/

#include <bits/stdc++.h>

using namespace std;
#define int long long 
typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll ;

#define File          freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define loop(i,f,d)   for(int i = f;i<d;i++)
#define loop2(j,f,d)  for(int j = f;j>=d;j--)
#define len(V)        V.size()
#define sep           ' '
#define endl          '\n'
#define pb(x)         push_back(x)
#define debug(x)      cerr  << "bug " << x << endl;
#define migmig        cin.tie(NULL);ios_base::sync_with_stdio(false);
#define fi            first
#define sec           second
#define popcount(x)   __builtin_popcount(x)
#define md(x)         (((x%MD)+MD)%MD)
#define all(V)        V.begin(),V.end()
#define Mp(a,b)       make_pair(a,b)
#define gaws(a,b)     (((b-a+1LL)*(a+b))/2LL)
#define vvi           vector<vector<int>>
#define setprec(x)    fixed << setprecision(x)

const ll N = 2e5 + 100, MD = 1e9 + 7;
const ll inf = 2e9 , riz = -2e9;
int n ;
struct edge{int u,v,w;};
vector<edge> e;
vector<int> W;
vvi tmp(N);
bool mark[N];
vector<pii> g[N];
int dp[N],dp2[N],ans[N];
vector<int> par(N),sz(N,1);
int getpar(int u){
    if(par[u] ==u) return u;
    return par[u] = getpar(par[u]);
}
void DSU(){
    loop(i,0,n+2) par[i] = i ;
    loop(i,0,n+2) sz[i] = 1;
}
void merge(int u,int v){
    u = getpar(u);
    v=getpar(v);
    if(sz[u] > sz[v]) swap(u,v);
    if(u==v) return ;
    par[u] = v;
    sz[v] += sz[u];
}


void dfs(int u){
    mark[u] = 1;
    dp[u] = sz[u];
    for(auto p : g[u]){
        if(!mark[p.fi]){
            dfs(p.fi);
            dp[u] += dp[p.fi];
        }
    }
}
void dfs2(int u){
    mark[u] = 1;
    for(auto p : g[u]){
        if(!mark[p.fi]){
            dp2[p.fi] = dp2[u] + dp[u] - dp[p.fi];
            ans[p.sec] = 2*dp2[p.fi]*dp[p.fi];
            dfs2(p.fi);
        }
    }
}
void compress(vector<int>* arr,int l,int r){
    vector<int> tmp;
    loop(i,l,r) tmp.pb((*arr)[i]);
    sort(all(tmp));
    tmp.resize(unique(all(tmp))-tmp.begin());
    loop(i,l,r) (*arr)[i] = lower_bound(all(tmp),(*arr)[i]) - tmp.begin() + 1;
}
int32_t main() {
    migmig
    cin >> n ;
    loop(i,0,n-1){
        int u,v,w;
        cin >> u >> v >> w;
        edge tmp = {u,v};
        e.pb(tmp);
        W.pb(w);
    }
    compress(&W,0,n-1);
    loop(i,0,n-1) tmp[W[i]].pb(i);
    DSU();
    loop(i,0,n+1){
        dp[i] = 0;
        dp2[i] = 0;
        ans[i] = 0;
    }
    loop(i,1,n){
        vector<int> stk;
        for(auto x : tmp[i]){
            stk.pb(getpar(e[x].u));
            stk.pb(getpar(e[x].v));
            g[getpar(e[x].u)].pb(Mp(getpar(e[x].v),x));
            g[getpar(e[x].v)].pb(Mp(getpar(e[x].u),x));
        }
        for(auto p : stk){
            if(!mark[p]) dfs(p);
        }
        for(auto p : stk) mark[p] = 0;
        for(auto p : stk){
            if(!mark[p]) dfs2(p);
        }
        for(auto p : stk){
            dp[p] = 0 ;
            dp2[p] =0;
            mark[p] = 0;
            g[p].clear();
        }
        for(auto x : tmp[i]){
            merge(e[x].u,e[x].v);
        }
        stk.clear();
    }
    int mx = *max_element(ans,ans+n);
    vector<int> re;
    loop(i,0,n-1){
        if(ans[i] == mx){
            re.pb(i);
        }
    }
    cout << mx << sep << len(re) << endl;
    for(auto x : re) cout << x+1 << sep;
    cout << endl;
    return 0;
}