fork(2) download
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. vector<long long> adj[100001];
  5. double down[100001];
  6. double up[100001];
  7. long long childcnt[100001];
  8. long long n,x,y;
  9. vector<long long> tim;
  10. double dfs(long long pos, long long par){
  11. long long cnt=0;
  12. double tot = 0;
  13. for(long long i : adj[pos]){
  14. if(i==par) continue;
  15. cnt++;
  16. tot+=dfs(i,pos);
  17. }
  18. double val = 0;
  19. if(cnt>0) tot/=cnt;
  20. down[pos]=val+tot;
  21. childcnt[pos]=cnt;
  22. return down[pos]+tim[pos];
  23. }
  24.  
  25. void dfs1(long long pos, long long par){
  26. up[pos]=tim[par];
  27. double val = down[par];
  28. val*=childcnt[par];
  29. val-=tim[pos];
  30. val-=down[pos];
  31. val+=up[par];
  32. if(par==1){
  33. if(childcnt[par]>1)
  34. val/=(childcnt[par]-1);
  35. }
  36. else{
  37. if(childcnt[par]>0)
  38. val/=(childcnt[par]);
  39. }
  40. up[pos]+=val;
  41. for(long long i : adj[pos]){
  42. if(i==par) continue;
  43. dfs1(i,pos);
  44. }
  45. }
  46. int main() {
  47. cin>>n;
  48. tim.resize(n+1);
  49. for(long long i = 1 ; i<=n ; i++) cin>>tim[i];
  50. for(long long i = 1; i<n ; i++){
  51. cin>>x>>y;
  52. adj[x].push_back(y);
  53. adj[y].push_back(x);
  54. }
  55. dfs(1,1);
  56. up[1]=0;
  57. for(long long i : adj[1])
  58. dfs1(i,1);
  59. double minval = 1e200;
  60. double minpos = -1;
  61. for(long long i = 1; i<=n; i++){
  62. double val = 0.0;
  63. if(childcnt[i]==0) val = up[i]+tim[i];
  64. else if(i==1) val=down[i]+tim[i];
  65. else{
  66. val = down[i]*childcnt[i];
  67. val+=up[i];
  68. val/=(childcnt[i]+1);
  69. val+=tim[i];
  70. }
  71. if(val<minval){
  72. minval = val;
  73. minpos = i;
  74. }
  75. }
  76. cout<<minpos;
  77. return 0;
  78. }
Success #stdin #stdout 0s 6980KB
stdin
7
2 3 3 5 1 2 1
1 2
4 5
5 3
3 1
1 7
2 6
stdout
1