fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5. const int MOD = 1000000007;
  6. const ll INF = (ll)1e18;
  7. const int MX = 1000001;
  8.  
  9. ll modExp(ll base, ll power) {
  10.     if (power == 0) return 1;
  11.     ll cur = modExp(base, power/2);
  12.     cur = (cur * cur) % MOD;
  13.     if (power & 1) cur = (cur * base) % MOD;
  14.     return cur;
  15. }
  16.  
  17. ll inv(ll x) { return modExp(x, MOD-2); }
  18. ll mul(ll A, ll B) { return (A*B) % MOD; }
  19. ll add(ll A, ll B) { A += B; if (A >= MOD) A -= MOD; return A; }
  20. ll sub(ll A, ll B) { A -= B; if (A < 0) A += MOD; return A; }
  21.  
  22. const int MAXN = 200005;
  23. int n;
  24. vector<int> adj[MAXN];
  25. ll arr[MAXN];
  26.  
  27. ll dp[MAXN];
  28. ll neg[MAXN], negsum[MAXN];
  29. ll pos[MAXN], possum[MAXN];
  30.  
  31. void dfs1(int u, int p) {
  32.     pos[u]++;
  33.     possum[u] += arr[u];
  34.     for (int v : adj[u]) {
  35.         if (v == p) continue;
  36.         dfs1(v, u);
  37.         pos[u]    += neg[v];
  38.         neg[u]    += pos[v];
  39.         possum[u] += negsum[v];
  40.         negsum[u] += possum[v];
  41.     }
  42.     possum[u]  += pos[u] * arr[u];
  43.     negsum[u]  += neg[u] * arr[u];
  44. }
  45.  
  46. void dfs2(int u, int p) {
  47.     // b was undefined – guessing you meant to combine both sums here:
  48.     dp[u] = add(possum[u] % MOD, negsum[u] % MOD);
  49.  
  50.     for (int v : adj[u]) {
  51.         if (v == p) continue;
  52.         ll newpossum = sub(possum[u], negsum[v]);
  53.         ll newnegsum = sub(negsum[u], possum[v]);
  54.         ll newneg    = sub(neg[u], pos[v]);
  55.         ll newpos    = sub(pos[u], neg[v]);
  56.         possum[v]    = add(possum[v], newnegsum);
  57.         negsum[v]    = add(negsum[v], newpossum);
  58.         neg[v]       = add(neg[v], newpos);
  59.         pos[v]       = add(pos[v], newneg);
  60.         dfs2(v, u);
  61.     }
  62. }
  63.  
  64. int main(){
  65.     ios::sync_with_stdio(false);
  66.     cin.tie(nullptr);
  67.  
  68.     cin >> n;
  69.     for (int i = 1; i <= n; i++) {
  70.         cin >> arr[i];
  71.     }
  72.     for (int i = 0; i < n-1; i++) {
  73.         int u,v;
  74.         cin >> u >> v;
  75.         adj[u].push_back(v);
  76.         adj[v].push_back(u);
  77.     }
  78.  
  79.     dfs1(1, 0);
  80.     dfs2(1, 0);
  81.  
  82.     ll res = 0;
  83.     for (int i = 1; i <= n; i++) {
  84.         res = add(res, dp[i]);
  85.     }
  86.     cout << res << "\n";
  87.     return 0;
  88. }
  89.  
Success #stdin #stdout 0.01s 13644KB
comments (?)
stdin
copy 
4
-4 1 5 -2
1 2
1 3
1 4
stdout
copy 
999999959
https://ideone.com/6h2qWT
language:
C++ (gcc 8.3)
created:
2 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!