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