fork download 
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC optimize("unroll-loops")
  3.  
  4. #include <bits/stdc++.h>
  5. #include <ext/pb_ds/assoc_container.hpp>
  6. #include <ext/pb_ds/tree_policy.hpp>
  7.  
  8. using namespace __gnu_pbds;
  9. using namespace std;
  10. using ll = long long;
  11.  
  12. template <typename T>
  13. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  14.  
  15. const ll mod = 1e9 + 7;
  16. const ll mod2 = 998244353;
  17.  
  18. ll gcd(ll a, ll b) {
  19.     return b ? gcd(b, a % b) : a;
  20. }
  21.  
  22. ll pow(ll a, ll b) {
  23.     ll ans = 1;
  24.     while (b) {
  25.         if (b & 1)
  26.             ans *= a;
  27.         b >>= 1;
  28.         a *= a;
  29.     }
  30.     return ans;
  31. }
  32.  
  33. ll pow(ll a, ll b, ll c) {
  34.     ll ans = 1;
  35.     while (b) {
  36.         if (b & 1)
  37.             ans = (ans * a) % c;
  38.         b >>= 1;
  39.         a = (a * a) % c;
  40.     }
  41.     return ans;
  42. }
  43.  
  44. vector<ll> seiveoferasthones(ll n) {
  45.     vector<bool> prime(n + 1, true);
  46.     prime[0] = false;
  47.     prime[1] = false;
  48.     for (int i = 2; i * i <= n; i++) {
  49.         if (prime[i]) {
  50.             for (int j = i * i; j <= n; j += i) {
  51.                 prime[j] = false;
  52.             }
  53.         }
  54.     }
  55.     vector<ll> primes;
  56.     for (ll i = 2; i <= n; i++) {
  57.         if (prime[i]) {
  58.             primes.push_back(i);
  59.         }
  60.     }
  61.     return primes;
  62. }
  63.  
  64. void check(bool b) {
  65.     cout << (b ? "Yes\n" : "No\n");
  66. }
  67.  
  68. // DFS
  69. void dfs(vector<vector<ll>> &adj, vector<bool> &visited, ll s) {
  70.     if (visited[s]) return;
  71.     visited[s] = true;
  72.     for (auto u : adj[s]) {
  73.         dfs(adj, visited, u);
  74.     }
  75. }
  76.  
  77. int main() {
  78.     ios_base::sync_with_stdio(false);
  79.     cin.tie(nullptr);
  80.     cout.tie(nullptr);
  81.  
  82.     int t = 1;
  83.     // cin >> t;
  84.     while (t--) {
  85.         ll n;
  86.         cin >> n;
  87.         vector<ll> vec(n + 1); 
  88.         for (int i = 1; i <= n; i++) {
  89.             cin >> vec[i];
  90.         }
  91.         vector<vector<pair<ll, ll>>> adj(n + 1);
  92.         map<pair<ll, ll>, ll> mpp;
  93.  
  94.         for (int i = 0; i < n - 1; i++) {
  95.             ll a, b, c;
  96.             cin >> a >> b >> c;
  97.             mpp[{a, b}] = c;
  98.             mpp[{b, a}] = c;
  99.             adj[a].push_back({b, c});
  100.             adj[b].push_back({a, c});
  101.         }
  102.  
  103.         queue<ll> q1;
  104.         vector <ll> pushed(n+1,0);
  105.         ll root = 1;
  106.         for (int i = 2; i <= n; i++) {
  107.             if (adj[i].size() == 1) {
  108.                 q1.push(i);
  109.                 pushed[i]= 1;
  110.             }
  111.         }
  112.  
  113.         queue<ll> q;
  114.         vector<bool> visited(n + 1, false);
  115.         vector<ll> parent(n + 1, 0);
  116.         visited[root] = true;
  117.         q.push(root);
  118.         while (!q.empty()) {
  119.             ll s = q.front();
  120.             q.pop();
  121.             for (auto u : adj[s]) {
  122.                 if (!visited[u.first]) {
  123.                     visited[u.first] = true;
  124.                     parent[u.first] = s;
  125.                     q.push(u.first);
  126.                 }
  127.             }
  128.         }
  129.         ll ans = 0;
  130.         while (!q1.empty()) {
  131.             ll s = q1.front();
  132.             q1.pop();
  133.             if (parent[s] == 0) continue; 
  134.  
  135.             ans += mpp[{s, parent[s]}] * abs(vec[s]);
  136.             vec[parent[s]] += vec[s];
  137.             vec[s] = 0;
  138.             if (parent[s] != 0 && pushed[parent[s]] == 0) {
  139.                 q1.push(parent[s]);
  140.                 pushed[parent[s]] = 1;
  141.             }
  142.         }
  143.  
  144.         cout << ans << '\n';
  145.     }
  146.  
  147.     return 0;
  148. }
  149.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
5
-2 -8 10 -2 2
3 5 1
1 3 5
2 5 0
3 4 6
stdout 
28
https://ideone.com/Du3tez
language:
C++14 (gcc 8.3)
created:
5 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!