609E - Minimum spanning tree for each edge - CodeForces Solution

#include <bits/stdc++.h>

using namespace std ; 
typedef long long int ll ; 
typedef pair<int,int> pii ; 
typedef pair<pii,int> piii ;
typedef pair<piii,int> piiii ; 
const ll maxn = 2e5 + 10 ; 
const int maxlg = 20 ; 
ll n , m , sz[maxn] , num[maxn] , mn[maxn][maxlg+1] , par[maxn][maxlg+1] , l  , edg , valve[maxn] , h[maxn]; 

set<piiii> s ;  
vector <pii> vec[maxn] ; 
vector <piiii> ans ; 
vector <int> tmp[maxn] ; 
bool vis[maxn] , mark[maxn] , ss[maxn] ; 

void dfs(ll x , ll p)
{
//	cout << p << " " << x << endl ; 
	vis[x] = true; 
	par[x][0] = p ; 
	for(int i=1 ; i<maxlg ; i++)
	{
		par[x][i] = par[par[x][i-1]][i-1] ; 
	}
	
	for(int i=0 ; i<vec[x].size() ; i++)
	{
		ll q = vec[x][i].first ;
		ll w = vec[x][i].second ;
		if(q == p)
		{
			mn[x][0] = w ; 
		} 
		if(vis[q] == false)
		{
			h[q]  =h[x] + 1 ; 
			edg += w ; 
			dfs(q, x) ; 
		}
	}
}

void two(ll x)
{
	mark[x] = true ; 
	
	for(int i=1 ; i<maxlg ; i++)
	{
	//	cout << mn[x][i-1] << "***" << mn[par[x][i-1]][i-1] << endl ; 
			mn[x][i] = max(mn[x][i-1] , mn[par[x][i-1]][i-1]) ;	
	//	cout << x << " " << i << " " << mn[x][i] << endl; 
	}
	
	for(int i=0 ; i<vec[x].size() ; i++)
	{
		ll q = vec[x][i].first ; 
		if(mark[q] == false)
		{
			two(q) ; 
		}
	}
}

void merge(ll x , ll y , ll z)
{
	ll x1 = num[x] , y1 = num[y] ; 
	if(sz[x1] < sz[y1])
	{
		swap(x,y) ; 
	}
	x1 = num[x] ;
	y1 = num[y] ;
	
	for(int i=0 ; i<tmp[y1].size() ; i++)
	{
		ll q =tmp[y1][i] ;
		num[q] = x1 ; 
		tmp[x1].push_back(q) ; 
	}
	
	pii pu , pv; 
	pu.first = y ; 
	pu.second = z ; 
	vec[x].push_back(pu) ;  
	pv.first = x ; 
	pv.second = z ; 
	vec[y].push_back(pv) ;
	sz[x1] += sz[y1] ; 	
}

int lca(ll u , ll v)
{
	if(h[u] < h[v])
	{
		swap(u,v) ; 
	}
	
	for(int i=maxlg ; i>=0 ; i--)
	{
		if(h[par[u][i]] >= h[v])
		{
			u = par[u][i] ; 
		}
	}
	
	if(u == v)
	{
		return u ; 
	}
	
	for(int i= maxlg ; i>=0 ; i--)
	{
		if(par[u][i] != par[v][i])
		{
			u = par[u][i] ; 
			v = par[v][i] ; 
		}
	}
	
	return par[u][0] ; 
}

int main()
{
	ios_base::sync_with_stdio(false) ; 
	cin >> n >> m ; 
	ll m1 = m ; 
	for(int i=1 ; i<=m ; i++)
	{
		ll u , v , w ; 
		cin >> u >> v >> w ; 
		piiii k ; 
		k.first.first.first = w;
		k.first.first.second = u;
		k.first.second = v;
		k.second = i ; 
		s.insert(k) ;
	}
	
	for(int i=1 ; i<=n ; i++)
	{
		num[i] = i ; 
		sz[i] = 1 ;
		tmp[i].push_back(i) ;  
	}
		
	while(m--)
	{
		piiii p = *s.begin() ;
		
		s.erase(*s.begin() ) ; 
		 
		ll w = p.first.first.first ; 
		ll u = p.first.first.second ; 
		ll v = p.first.second ; 
			
		if(num[v] != num[u])
		{ 
			merge(u , v , w) ; 
		}
		else 
		{
			ans.push_back(p) ; 
		}
	}
	
	dfs(1 , 0) ; 
	
	two(1) ; 
	
	
	for(int i=0 ; i<ans.size() ; i++)
	{
		ll w = ans[i].first.first.first ;
		ll u = ans[i].first.first.second ; 
		ll v = ans[i].first.second ; 
		ll j = ans[i].second ; 
	//	cout << u << " " << v << " " << w << " " << j << endl;
	//	cout << h[u] << "<->" << h[v] << endl ; 
		ll lc = lca(u , v) ; 
		if(lc == 0)
		{
			lc = 1 ; 
		}
		// cout << lc << endl ; 
		ll xu[maxlg] , xv[maxlg] ; 
		ll hu = h[u] - h[lc] , hv = h[v] - h[lc] , k1 = -1 , k2 = -1; 
		
		for(int i=0 ; i<maxlg ; i++)
		{
			xu[i] = hu%2 ; 
			hu /= 2 ; 
			xv[i] = hv % 2 ; 
			hv /=2 ; 
		}
		
		for(int i=0 ; i<maxlg ; i++)
		{
			if(xu[i] == 1)
			{
				//cout << i << " ----" << u << endl; 
			//	cout << k1 << "  <>  " << mn[u][i] << "<>" << u << endl; 
				k1 = max(k1 , mn[u][i]) ; 
				u = par[u][i] ; 
			//	cout << u << "*" << endl ; 
			}
			
			if(xv[i] == 1)
			{
			//	cout << i <<  "*******" << v << endl;
			//	cout << k2 << " ++++ " << mn[v][i] << endl  ;   
				k2 = max(k2 , mn[v][i]) ; 
				v = par[v][i] ;
			}
		}
		ll ee = max(k1 , k2) ; 
	//	cout << ee << "<<<" << endl ; 
	//	cout << edg << " %% " << endl;
		valve[j] = edg - ee + w ; 
	//	cout << valve[j] << "))))" << endl ;
	}
	
	for(int i=1 ; i<=m1 ; i++)
	{	
		if(valve[i] == 0)
		{
			cout << edg << endl; 
		}
		else 
		{
			cout << valve[i] << endl ; 
		}
		
	}
	
	
	
}