fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <queue>
  5. #include <map>
  6. #include <stack>
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9. #include <ext/pb_ds/assoc_container.hpp>
  10. using namespace __gnu_pbds;
  11. template <class T>
  12. using orderStaticTree =
  13.     tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  14.  
  15. #define ll long long
  16.  
  17. #define saleh                         \
  18.     ios_base::sync_with_stdio(false); \
  19.     cin.tie(nullptr);
  20.  
  21. const int md = 1e9 + 7;
  22. #define ll long long
  23.  
  24. const ll remo = -1e18;
  25. ll sumBeforWeak = 0;
  26. stack<int> firstLayer;
  27.  
  28. void dfs(int node, vector<vector<int>> &adj, vector<bool> &vis, map<pair<int, int>, int> mp, vector<int> &val)
  29. {
  30.     vis[node] = 1;
  31.     sumBeforWeak += val[node];
  32.     for (auto i : adj[node])
  33.     {
  34.         if (!vis[i])
  35.         {
  36.             if (mp[{node, i}] == 1)
  37.             {
  38.                 dfs(i, adj, vis, mp, val);
  39.             }
  40.             else
  41.             {
  42.                 firstLayer.push(i);
  43.             }
  44.         }
  45.     }
  46. }
  47.  
  48. void dfs2(int root, int par, int node, vector<vector<int>> &adj, vector<vector<int>> &adj2,
  49.           vector<bool> &vis, map<pair<int, int>, int> mp, vector<int> &val, vector<ll> &Gen)
  50. {
  51.  
  52.     vis[node] = 1;
  53.     Gen[root] += val[node];
  54.     for (auto i : adj[node])
  55.     {
  56.         if (!vis[i])
  57.         {
  58.             if (mp[{node, i}] == 0)
  59.             {
  60.                 adj2[root].push_back(i);
  61.             }
  62.             else
  63.             {
  64.                 dfs2(root, node, i, adj, adj2, vis, mp, val, Gen);
  65.             }
  66.         }
  67.     }
  68.  
  69.     for (auto i : adj2[root])
  70.     {
  71.         dfs2(i, i, i, adj, adj2, vis, mp, val, Gen);
  72.     }
  73. }
  74.  
  75. ll rec(int node, vector<vector<int>> &adj2, vector<ll> &Gen)
  76. {
  77.     if (adj2[node].size() == 0)
  78.         return Gen[node];
  79.     ll maxi = 0;
  80.     for (auto i : adj2[node])
  81.     {
  82.         maxi = max(maxi, rec(i, adj2, Gen));
  83.     }
  84.     return Gen[node] + maxi;
  85. }
  86.  
  87. int main()
  88. {
  89.     saleh;
  90.     int t;
  91.     cin >> t;
  92.     while (t--)
  93.     {
  94.         sumBeforWeak = 0;
  95.         stack<int> st2;
  96.         firstLayer = st2;
  97.  
  98.         int n;
  99.         cin >> n;
  100.         map<pair<int, int>, int> mp;
  101.         vector<int> val(n);
  102.         for (auto &i : val)
  103.             cin >> i;
  104.         vector<vector<int>> adj(n, vector<int>());
  105.         for (int u, v, s, i = 0; i < n - 1; i++)
  106.         {
  107.             cin >> u >> v >> s;
  108.             --u;
  109.             --v;
  110.             adj[u].push_back(v);
  111.             adj[v].push_back(u);
  112.             mp[{u, v}] = mp[{v, u}] = s;
  113.         }
  114.         vector<bool> vis(n);
  115.  
  116.         dfs(0, adj, vis, mp, val);
  117.         vector<ll> Gen(n);
  118.         Gen[0] = sumBeforWeak;
  119.  
  120.         vector<vector<int>> adj2(n, vector<int>());
  121.         while (!firstLayer.empty())
  122.         {
  123.             int u = firstLayer.top();
  124.             // cout<<u+1<<" ";
  125.             firstLayer.pop();
  126.             adj2[0].push_back(u);
  127.         }
  128.         // cout<<endl;
  129.         // cout<<sumBeforWeak<<endl;
  130.  
  131.         for (auto i : adj2[0])
  132.         {
  133.             dfs2(i, i, i, adj, adj2, vis, mp, val, Gen);
  134.         }
  135.         cout << rec(0, adj2, Gen) << endl;
  136.     }
  137.  
  138.     return 0;
  139. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/E527DR
language:
C++ (gcc 8.3)
created:
6 hours 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!