fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using i128 = __int128_t;
  5.  
  6. int main() {
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(nullptr);
  9.  
  10.     int n;
  11.     if(!(cin >> n)) return 0;
  12.     vector<vector<pair<int,int>>> g(n+1);
  13.     for(int i=0;i<n-1;i++){
  14.         int a,b,w; cin>>a>>b>>w;
  15.         g[a].push_back({b,w});
  16.         g[b].push_back({a,w});
  17.     }
  18.  
  19.     vector<int> par(n+1,-1), pw(n+1,0), order;
  20.     order.reserve(n);
  21.     stack<int> st; st.push(1); par[1]=0;
  22.     while(!st.empty()){
  23.         int u=st.top(); st.pop();
  24.         order.push_back(u);
  25.         for(auto [v,w]: g[u]) if(v!=par[u]){
  26.             par[v]=u; pw[v]=w; st.push(v);
  27.         }
  28.     }
  29.  
  30.     vector<long long> sz(n+1,1);
  31.     vector<i128> downDist(n+1,0), downSq(n+1,0);
  32.     for(int i=n-1;i>=0;i--){
  33.         int u=order[i];
  34.         for(auto [v,w]: g[u]) if(v!=par[u]){
  35.             sz[u]+=sz[v];
  36.             downDist[u]+=downDist[v] + (i128)sz[v]*w;
  37.             downSq[u]+=downSq[v] + (i128)2*w*downDist[v] + (i128)sz[v]*(i128)w*w;
  38.         }
  39.     }
  40.  
  41.     vector<i128> D(n+1,0), S(n+1,0);
  42.     D[1]=downDist[1]; S[1]=downSq[1];
  43.     for(int u: order){
  44.         for(auto [v,w]: g[u]) if(v!=par[u]){
  45.             D[v]=D[u] + (i128)w*((i128)n - 2*(i128)sz[v]);
  46.             i128 sumA = downDist[v] + (i128)sz[v]*w;
  47.             S[v]=S[u] + (i128)n*(i128)w*w + (i128)2*w*( D[u] - 2*sumA );
  48.         }
  49.     }
  50.  
  51.     i128 best = S[1];
  52.     for(int i=2;i<=n;i++) if(S[i]<best) best=S[i];
  53.     vector<int> res;
  54.     for(int i=1;i<=n;i++) if(S[i]==best) res.push_back(i);
  55.  
  56.     cout << res.size() << "\n";
  57.     for(size_t i=0;i<res.size();i++){
  58.         if(i) cout << ' ';
  59.         cout << res[i];
  60.     }
  61.     cout << "\n";
  62.     return 0;
  63. }
  64.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
6
6 3 35
5 2 12
4 5 31
4 6 14
3 1 40
stdout
copy 
1
6
https://ideone.com/Iv1BXM
language:
C++14 (gcc 8.3)
created:
12 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!