fork download
copy 
  1. //
  2. //  main.cpp
  3. //  Practice
  4. //
  5. //  Created by Neel Shah on 11/27/14.
  6. //  Copyright (c) 2014 Neel Shah. All rights reserved.
  7. //
  8.  
  9. #include <iostream>
  10. #include <stdio.h>
  11. #include <algorithm>
  12. #include <vector>
  13. #include <string.h>
  14. #include <string>
  15. #include <map>
  16. #include<stack>
  17. #include<map>
  18. #include<queue>
  19. #include <math.h>
  20. #include<set>
  21. #include<stdint.h>
  22. #include <utility>
  23. #define MAXN 100005
  24. #define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
  25.  
  26. using namespace std;
  27. typedef long long int ll;
  28. typedef pair<int, int> mp;
  29. template<class T> void chmin(T &t, const T &f) { if (t > f) t = f; }
  30. template<class T> void chmax(T &t, const T &f) { if (t < f) t = f; }
  31.  
  32. int t[MAXN], n, i;
  33. vector<int> adj[MAXN];
  34. map<int , map<int, double> > dp;
  35. double mini = 1000000;
  36. int ans;
  37.  
  38. double sol(int s, int p)
  39. {
  40.     if(dp.count(p) && dp[p].count(s))
  41.         return dp[p][s];
  42.  
  43.     double ret = t[s] + 0.0, tot = 0.0;
  44.  
  45.     for(int i=0; i<adj[s].size(); ++i)
  46.     {
  47.         int to = adj[s][i];
  48.         if(to == p)
  49.             continue;
  50.         dp[s][to] = sol(to, s);
  51.         tot += dp[s][to];
  52.     }
  53.  
  54.     if(p == 0)
  55.         tot /= adj[s].size();
  56.     else if(adj[s].size()-1 != 0)
  57.         tot /= adj[s].size()-1;
  58.  
  59.     return ret += tot;
  60. }
  61.  
  62. int main()
  63. {
  64.     scanf("%d", &n);
  65.     for(i=1; i<=n; ++i)
  66.         scanf("%d", &t[i]);
  67.     for(i=1; i<n; ++i)
  68.     {
  69.         int x, y;
  70.         scanf("%d %d", &x, &y);
  71.         adj[x].push_back(y);
  72.         adj[y].push_back(x);
  73.     }
  74.  
  75.     for(int i=1; i<=n; ++i)
  76.     {
  77.         double val = sol(i, 0);
  78.         if(val < mini)
  79.         {
  80.             mini = val;
  81.             ans = i;
  82.         }
  83.     }
  84.  
  85.     printf("%d", ans);
  86.     return 0;
  87. }
Success #stdin #stdout 0s 4840KB
comments (?)
stdin
copy 
5
2 2 1 2 2
1 2
2 3
3 4
4 5
stdout
copy 
3
https://ideone.com/qma94w
language:
C++ (gcc 8.3)
created:
9 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!