Untitled
unknown
c_cpp
a year ago
1.1 kB
3
Indexable
Never
#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; }