SHARE
TWEET

Untitled

a guest Dec 4th, 2018 409 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string.h>
  3. #include <vector>
  4. using namespace std;
  5. vector<int> v[500005];
  6. int m=1,a[500005],dp[20][500005];
  7. long long ans;
  8. void dfs(int node,int p)
  9. {
  10.     dp[0][node]=p;
  11.     for (int i=1;i<20;i++)
  12.     {
  13.         if (dp[i-1][node]!=-1)
  14.         dp[i][node]=dp[i-1][dp[i-1][node]];
  15.     }
  16.     int d;
  17.     long long mn=(1LL<<60);
  18.     for (d=0;d<20 && dp[d][node]!=-1;d++)
  19.     mn=min(mn,(long long)(d+1)*a[dp[d][node]]+a[node]);
  20.     mn=min(mn,(long long)(d+1)*a[m]+a[node]);
  21.     if (p!=-1)
  22.     ans+=mn;
  23.     for (int u:v[node])
  24.     {
  25.         if (u!=p)
  26.         dfs(u,node);
  27.     }
  28. }
  29. int main()
  30. {
  31.     int n;
  32.     scanf("%d",&n);
  33.     for (int i=1;i<=n;i++)
  34.     {
  35.         scanf("%d",&a[i]);
  36.         if (a[i]<a[m])
  37.         m=i;
  38.     }
  39.     for (int i=1;i<n;i++)
  40.     {
  41.         int a,b;
  42.         scanf("%d%d",&a,&b);
  43.         v[a].push_back(b);
  44.         v[b].push_back(a);
  45.     }
  46.     memset(dp,-1,sizeof(dp));
  47.     dfs(m,-1);
  48.     printf("%I64d",ans);
  49. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top