fork(9) download
copy 
  1. #include <vector>
  2. #include <list>
  3. #include <map>
  4. #include <set>
  5. #include <queue>
  6. #include <deque>
  7. #include <stack>
  8. #include <bitset>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <numeric>
  12. #include <utility>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <iomanip>
  16. #include <cstdio>
  17. #include <cmath>
  18. #include <cstdlib>
  19. #include <ctime>
  20. #include <cstring>
  21. #include <cassert>
  22. #include <tr1/unordered_map>
  23.  
  24. using namespace std;
  25. using namespace tr1;
  26.  
  27. typedef pair<int, int> pi;
  28. typedef long long ll;
  29. typedef long double ld;
  30.  
  31. const int N = 1e5 + 5;
  32.  
  33. vector< int > v;
  34. vector< int > adj[N];
  35.  
  36. unordered_map<int, unordered_map<int, ld> > dp;
  37. unordered_map<int, unordered_map<int, ld> > done;
  38. ld memo[N];
  39.  
  40.  
  41. ld solve(int cur, int par){
  42.     if(dp.count(cur) && dp[cur].count(par)){
  43.         return dp[cur][par];
  44.     }
  45.     ld &ret = dp[cur][par];
  46.     ret = v[cur];
  47.     ld tot = 0;
  48.     if(done.count(cur) && done[cur].size() == adj[cur].size()){
  49.         if(par != 0){
  50.             tot = memo[cur] - done[cur][par];
  51.         }else{
  52.             tot = memo[cur];
  53.         }
  54.     }else{
  55.         for(int i = 0; i < adj[cur].size(); i++){
  56.             int to = adj[cur][i];
  57.             if(to == par) continue;
  58.             ld val = solve(to, cur);
  59.             if(done[cur].count(to) == 0){
  60.                 done[cur][to] = val;
  61.                 memo[cur] += val;
  62.             }
  63.             tot += val;
  64.         }
  65.     }
  66.     if(adj[cur].size() - (par != 0) != 0) tot /= adj[cur].size() - (par != 0);
  67.     ret += tot;
  68.     return ret;
  69. }
  70.  
  71. int main(){
  72. #ifndef ONLINE_JUDGE
  73.     freopen("in.in", "r", stdin);
  74.     //freopen("out.out", "w", stdout);
  75. #endif
  76.     ios::sync_with_stdio(false);
  77.     cin.tie(0);
  78.  
  79.     int n, x, a, b;
  80.     cin >> n;
  81.     v.push_back(0);
  82.     for(int i = 0; i < n; i++){
  83.         cin >> x;
  84.         v.push_back(x);
  85.     }
  86.     for(int i = 1; i < n; i++){
  87.         cin >> a >> b;
  88.         adj[a].push_back(b);
  89.         adj[b].push_back(a);
  90.     }
  91.  
  92.     ld best = 1e200;
  93.     int ans = -1;
  94.     for(int i = 1; i <= n; i++){
  95.         ld cur = solve(i, 0);
  96.         if(cur < best){
  97.             best = cur;
  98.             ans = i;
  99.         }
  100.     }
  101.  
  102.     cout << ans << endl;
  103.  
  104.     return 0;
  105. }
  106.  
Success #stdin #stdout 0s 5620KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/pPlbTB
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!