fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define MOD 1000000007
  5. #define maxn 1000006
  6. #define base 9997
  7. #define pd pair<ll, ll>
  8. #define fi first
  9. #define se second
  10. #define bitmask(mask,i) ((mask>>i)&1)
  11. #define __KezzyBlue__ signed main()
  12. ll n, c[maxn], nx[maxn];
  13. pd dp[maxn], ans[maxn];
  14. vector<ll> a[maxn];
  15. pd merge(pd a, pd b)
  16. {
  17.     pd c;
  18.     c.fi = a.fi * b.fi;
  19.     c.se = a.se + b.se;
  20.     return c;
  21. }
  22. bool operator >(pd a, pd b) {
  23.     return a.first * b.second > b.first * a.second;
  24. }
  25. bool operator <(pd a, pd b) {
  26.     return a.first * b.second < b.first * a.second;
  27. }
  28. void dfs(ll u, ll par = -1)
  29. {
  30.     dp[u] = {c[u], 1};
  31.     pd cur = dp[u];
  32.     for(int v : a[u])
  33.     {
  34.         if(v != par)
  35.         {
  36.             dfs(v, u);
  37.             if(dp[u] > merge(cur, dp[v]))
  38.             {
  39.                 dp[u] = merge(cur, dp[v]);
  40.                 nx[u] = v;
  41.             }
  42.         }
  43.     }
  44. }
  45. void daogoc(ll u, ll par = -1)
  46. {
  47. //    cout << dp[u].fi << " " << dp[u].se << "\n";
  48. //    cout << u << " " << nx[u] << "\n";
  49.     ans[u] = dp[u];
  50.     pd maxs = {c[u], 1};
  51.     for(int v : a[u])
  52.     {
  53.         if(v != nx[u])
  54.         {
  55.             if(maxs > merge({c[u], 1}, dp[v]))
  56.             {
  57.                 maxs = merge({c[u], 1}, dp[v]);
  58.             }
  59.  
  60.         }
  61.     }
  62.     for(int v : a[u])
  63.     {
  64.         if(v != par)
  65.         {
  66.             pd old_dp_u = dp[u];
  67.             pd old_dp_v = dp[v];
  68.             if(nx[u] != v)
  69.             {
  70.                 if(dp[v] > merge({c[v], 1}, dp[u]))
  71.                 {
  72.                     dp[v] = merge({c[v], 1}, dp[u]);
  73.                     nx[v] = u;
  74.                 }
  75.             }
  76.             else
  77.             {
  78.                 dp[u] = maxs;
  79.                 if(dp[v] > merge({c[v], 1}, dp[u]))
  80.                 {
  81.                     dp[v] = merge({c[v], 1}, dp[u]);
  82.                     nx[v] = u;
  83.                 }
  84.             }
  85.             daogoc(v, u);
  86.             dp[u] = old_dp_u;
  87.             dp[v] = old_dp_v;
  88.         }
  89.     }
  90. }
  91. __KezzyBlue__
  92. {
  93.     ios_base::sync_with_stdio(false);
  94.     cin.tie(NULL);
  95.     cout.tie(NULL);
  96.     cin >> n;
  97.     for(int i = 1; i < n; i++)
  98.     {
  99.         ll u, v;
  100.         cin >> u >> v;
  101.         a[u].push_back(v);
  102.         a[v].push_back(u);
  103.     }
  104.     for(int i = 1; i <= n; i++)
  105.         cin >> c[i];
  106.     dfs(1);
  107.     daogoc(1);
  108.     pd mins = {1e18, 1};
  109. //    for(ll i = 1; i <= n; i++) cout << ans[i].fi << " " << ans[i].se << "\n";
  110.     for(int i = 1; i <= n; i++)
  111.         if(mins > ans[i])
  112.             mins = ans[i];
  113.     ll cur = __gcd((ll)mins.fi, (ll)mins.se);
  114.     cout << mins.fi / cur << "/" << mins.se / cur;
  115. }
  116. // _   _                       ___   _
  117. //( ) ( )                     (  _ \(_ )
  118. //| |/ /   __  ____ ____ _   _| (_) )| | _   _   __
  119. //|   (  / __ \_   )_   ) ) ( )  _ ( | |( ) ( )/ __ \
  120. //| |\ \(  ___// /_ / /_| (_) | (_) )| || (_) |  ___/
  121. //(_) (_)\____)____)____)\__  |____/(___)\___/ \____)
  122. //                      ( )_| |
  123. //                       \___/
  124. //               _,........__
  125. //            ,-'            "`-.
  126. //          ,'                   `-.
  127. //        ,'                        \
  128. //      ,'                           .
  129. //      .'\               ,"".       `
  130. //     ._.'             /   `       \
  131. //     |   |            `-.'  ||       `.
  132. //     |   |            '-._,'||       | \
  133. //     .`.,'             `..,'.'       , |`-.
  134. //     l                       .'`.  _/  |   `.
  135. //     `-.._'-   ,          _ _'   -" \  .     `
  136. //`."""""'-.`-...,---------','         `. `....__.
  137. //.'        `"-..___      __,'\          \  \     \
  138. //\_ .          |   `""""'    `.           . \     \
  139. //  `.          |              `.          |  .     L
  140. //    `.        |`--...________.'.        j   |     |
  141. //      `._    .'      |          `.     .|   ,     |
  142. //         `--,\       .            `7""' |  ,      |
  143. //            ` `      `            /     |  |      |    _,-'"""`-.
  144. //             \ `.     .          /      |  '      |  ,'          `.
  145. //              \  v.__  .        '       .   \    /| /              \
  146. //               \/    `""\"""""""`.       \   \  /.''                |
  147. //                `        .        `._ ___,j.  `/ .-       ,---.     |
  148. //                ,`-.      \         ."     `.  |/        j     `    |
  149. //               /    `.     \       /         \ /         |     /    j
  150. //              |       `-.   7-.._ .          |"          '         /
  151. //              |          `./_    `|          |            .     _,'
  152. //              `.           / `----|          |-............`---'
  153. //                \          \      |          |
  154. //               ,'           )     `.         |
  155. //                7____,,..--'      /          |
  156. //
  157.  
Success #stdin #stdout 0.01s 29420KB
comments (?)
stdin 
Standard input is empty
stdout 
1000000000000000000/1
https://ideone.com/8wMWcv
language:
C++ (gcc 8.3)
created:
9 days 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!