This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int N = 2e5 + 5;
vector<pair<int,ll>> adj[N];
ll dp_down[N] , dp_up[N];
void dfs(int node,int par){
for(auto [ch,c] : adj[node]){
if(ch == par) continue;
dfs(ch,node);
dp_down[node] = max(dp_down[node] , dp_down[ch]+c);
}
}
void dfs2(int node,int par){
pair<ll,ll> mx;
for(auto [ch,c] : adj[node]){
if(ch == par) continue;
if(mx.first < dp_down[ch]) {
swap(mx.first,mx.second);
mx.first = dp_down[ch];
}
else if(mx.second < dp_down[ch]){
mx.second = dp_down[ch];
}
}
for(auto [ch,c] : adj[node]){
if(ch == par) continue;
ll x = 0;
if(mx.first == dp_down[ch]) x = mx.second;
else x = mx.first;
dp_up[ch] = max(dp_up[node] , x);
dfs2(ch,node);
}
}
void solve(){
int n,k;
cin>>n>>k;
for(int i=0;i<n-1;i++){
int a,b,c;
cin>>a>>b>>c;
adj[a].push_back({b,c});
adj[b].push_back({a,c});
}
dfs(1,0);
dfs2(1,0);
pair<ll,int> ans = {1e18,0};
for(int i=1;i<=n;i++) ans = min(ans , {max(dp_down[i] , dp_up[i]),i});
cout<<ans.first<<endl<<ans.second<<endl;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t=1;
//cin>>t;
while(t--){
solve();
}
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'void dfs(int, int)':
Main.cpp:9:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
9 | for(auto [ch,c] : adj[node]){
| ^
Main.cpp: In function 'void dfs2(int, int)':
Main.cpp:17:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
17 | for(auto [ch,c] : adj[node]){
| ^
Main.cpp:27:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
27 | for(auto [ch,c] : adj[node]){
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |