daily pastebin goal
68%
SHARE
TWEET

Untitled

a guest Dec 4th, 2018 492 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. int a[300005],k;
  5. long long dp[300005],ans=-1e9;
  6. vector<int> v[300005];
  7. void dfs(int node,int p,bool f)
  8. {
  9.     dp[node]=a[node];
  10.     for (int u:v[node])
  11.     {
  12.         if (u!=p)
  13.         {
  14.             dfs(u,node,f);
  15.             dp[node]+=max(dp[u],0LL);
  16.         }
  17.     }
  18.     if (f)
  19.     ans=max(ans,dp[node]);
  20.     else if (dp[node]==ans)
  21.     {
  22.         dp[node]=0;
  23.         k++;
  24.     }
  25. }
  26. int main()
  27. {
  28.     int n;
  29.     scanf("%d",&n);
  30.     for (int i=1;i<=n;i++)
  31.     scanf("%d",&a[i]);
  32.     for (int i=1;i<n;i++)
  33.     {
  34.         int a,b;
  35.         scanf("%d%d",&a,&b);
  36.         v[a].push_back(b);
  37.         v[b].push_back(a);
  38.     }
  39.     dfs(1,0,1);
  40.     dfs(1,0,0);
  41.     printf("%I64d %d",ans*k,k);
  42. }
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