Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
1.1 kB
3
Indexable
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define ll long long;
const int maxn = 1e5+7;
using namespace std ;
int dp1[maxn] , dp2[maxn] , ras;
vector<int> adj[maxn];
vector<pair<int,int>> vec[maxn];
bool mark[maxn];

void dfs(int u){
	mark[u] = true;
	int mx1 = 0 , mx2 = 0 , weight;
	for(auto v : adj[u]){
		if(!mark[v]){
			dfs(v);
			for(int i = 0 ; i < vec[u].size(); i++)
				if(vec[u][i].first == v) weight = vec[u][i].second;
		//	cout << weight << ' ';	
			int child = dp2[v] + weight;
			dp2[u] = max(child , dp2[u]);
			if(child > mx1)
				mx2 = mx1  , mx1 = child;
			else if (child > mx2)
				mx2 = child;			 
			dp1[u] = max(dp1[v] , mx1 + mx2);
		}
	}
	//cout << max(dp1[u] , dp2[u]);
	ras = u;
}
int main(){
	int n, m;
	cin >> n;
	m = n-1;
	for(int i = 0 ; i < m ; i++){
		int u , v , w;
		cin >> u >> v >> w;
		--u;--v;
		vec[u].push_back({v, w});
		vec[v].push_back({u , w});
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(0);
	cout << max(dp1[ras] , dp2[ras]);
	return 0;
}