fork download
copy 
  1. #pragma comment(linker, "/STACK:116777216")
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cstring>
  5. #include <string>
  6. #include <map>
  7. #include <set>
  8. #include <vector>
  9. #include <algorithm>
  10. #include <queue>
  11. #include <bitset>
  12. #include <stack>
  13. #include <iostream>
  14. #include <fstream>
  15. #include <cmath>
  16.  
  17.  
  18. #define sqr(a) ((a)*(a))
  19. #define odd(a) ((a)&1)
  20. #define foru(i,n) for (int i=0;i<(n);i++)
  21. #define ford(i,n) for (int i=(n)-1;i>=0;i--)
  22. #define forab(i,l,r) for (int i=(l);i<=(r);i++)
  23. #define forabd(i,r,l) for (int i=(r);i>=(l);i--)
  24. #define pb push_back
  25. #define F first
  26. #define S second
  27. #define all(x) x.begin(),x.end()
  28. #define sz(__X) (int)__X.size()
  29. #define pii pair<int,int>
  30. #define pb push_back
  31. #define mp make_pair
  32. #define ll long long
  33.  
  34. const double eps=1e-19;
  35. const double PI=acos(-1.0);
  36. const int INF=1000*1000*1000+7;
  37. const int MAXN = 100500;
  38.  
  39. using namespace std;
  40.  
  41. struct ver{
  42.     int pr;
  43.     long long sum_kv;
  44.     long long sum_way;
  45.     long long kol;
  46.     long long rast;
  47. };
  48.  
  49. int n;
  50. vector< pii > g[MAXN];
  51. ver a[MAXN];
  52. long long ans;
  53. vector<int> mas_ans;
  54.  
  55. void dfs(int v, int pr, long long rast)
  56. {
  57.     a[v].pr = pr;
  58.     a[v].kol = 1;
  59.     a[v].rast = rast;
  60.     a[v].sum_way = rast;
  61.     a[v].sum_kv = sqr(rast);
  62.     for (int i=0; i<sz(g[v]); i++)
  63.     {
  64.         int u=g[v][i].F;
  65.         int cost = g[v][i].S;
  66.         if ( u != pr)
  67.         {
  68.             dfs(u, v, (ll)(a[v].rast + cost));
  69.             a[v].sum_way += a[u].sum_way;
  70.             a[v].sum_kv += a[u].sum_kv;
  71.             a[v].kol += a[u].kol;
  72.         }
  73.     }
  74. }
  75.  
  76. void dfs_ans(int v, long long sum_rast, long long sum_kv, long long cost, int pr)
  77. {
  78.     long long sum_pr = sum_kv + (a[0].kol-a[v].kol)*sqr(cost) +
  79.                         2*cost*(sum_rast);
  80.     long long sum_pot = 0;
  81.     sum_rast += (a[0].kol-a[v].kol)*cost;
  82.     sum_kv = sum_pr;
  83.     for (int i=0; i<sz(g[v]); i++)
  84.     {
  85.         int u = g[v][i].F;
  86.         long long rebro = g[v][i].S;
  87.         if ( u != pr)
  88.         {
  89.             sum_pot += a[u].sum_kv + (a[u].kol)*sqr(a[v].rast) - 2*(a[v].rast)*(a[u].sum_way);
  90.             sum_rast += a[u].sum_way - a[u].kol*a[v].rast;
  91.         }
  92.     }
  93.     if ( ans > sum_pot + sum_pr)
  94.     {
  95.         ans = sum_pr + sum_pot;
  96.         mas_ans.clear();
  97.         mas_ans.pb(v);
  98.     }
  99.     else if ( sum_pr + sum_pot == ans)
  100.     {
  101.         mas_ans.pb(v);
  102.     }
  103.     for (int i=0; i<sz(g[v]); i++)
  104.     {
  105.         int u = g[v][i].F;
  106.         long long rebro = g[v][i].S;
  107.         if ( u != pr)
  108.         {
  109.             dfs_ans(u, sum_rast-( a[u].sum_way - a[u].kol*a[v].rast ),
  110.                     sum_kv + sum_pot - ( a[u].sum_kv + (a[u].kol)*sqr(a[v].rast) - 2*(a[v].rast)*(a[u].sum_way)),
  111.                     rebro, v);
  112.         }
  113.     }
  114. }
  115.  
  116. int main()
  117. {
  118.     freopen("bfs.in", "r", stdin);
  119.     freopen("bfs.out", "w", stdout);
  120.     scanf("%d", &n);
  121.     for (int i=1; i<n; i++)
  122.     {
  123.         int va, vb,vc;
  124.         scanf("%d %d %d",&va, &vb, &vc);
  125.         va--; vb--;
  126.         g[va].pb(mp(vb,vc));
  127.         g[vb].pb(mp(va,vc));
  128.     }
  129.     dfs(0, -1, 0);
  130.     ans = INF-7;
  131.     ans = ans*1000*1000*100;
  132.     dfs_ans(0, 0, 0, 0, -1);
  133.     cout<<sz(mas_ans)<<"\n";
  134.     for (int i=0; i<sz(mas_ans); i++)
  135.         cout<<mas_ans[i]+1<< " ";
  136.     return 0;
  137. }
Success #stdin #stdout 0.01s 7520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wf0j9T
language:
C++ (gcc 8.3)
created:
11 years 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!