Từ Trường THPT chuyên Lương Văn Tụy, Ninh Bình
Thông tin
include <bits/stdc++.h>
define int long long
using namespace std;
const int maxn = 50005;
vector<pair<int,int>> adj[maxn]; int d[maxn]; int res = 1e9; int u0 = 1; int sum = 0; int par[maxn]; void dfs(int u,int p){
for(auto [v,w] : adj[u]){
if(v != p){
par[v] = u;
d[v] = d[u] + w;
dfs(v,u);
}
}
if(d[u0] < d[u]){
u0 = u;
}
}
signed main() { // freopen("inp","r",stdin); // freopen("out","w",stdout); iosbase::syncwithstdio(0); cin.tie(0); cout.tie(0); int n; int u,v,w; cin >> n; for(int i = 0; i < n - 1; ++i){ cin >> u >> v >> w; adj[u].pushback({v,w}); adj[v].push_back({u,w}); } dfs(1,0); //cout << u0 << '\n';
memset(d, 0, sizeof d);
memset(par, 0, sizeof par);
int v0 = u0;
u0 = 0;
dfs(v0,0);
//cout << u0 << '\n';
int i = u0;
while(i != 0){
res = min(res ,max(d[i],d[u0] - d[i]));
i = par[i];
}
cout << res;
}