fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5.  
  6. const ll INF = (ll)4e18;
  7.  
  8. struct Dinic {
  9.     struct Edge {
  10.         int v;
  11.         ll cap;
  12.         int rev;
  13.     };
  14.  
  15.     int n;
  16.     vector<vector<Edge>> g;
  17.     vector<int> level, cur;
  18.  
  19.     Dinic(int n) : n(n) {
  20.         g.resize(n + 1);
  21.         level.resize(n + 1);
  22.         cur.resize(n + 1);
  23.     }
  24.  
  25.     void addEdge(int u, int v, ll c) {
  26.         Edge a = {v, c, (int)g[v].size()};
  27.         Edge b = {u, 0, (int)g[u].size()};
  28.  
  29.         g[u].push_back(a);
  30.         g[v].push_back(b);
  31.     }
  32.  
  33.     bool bfs(int s, int t) {
  34.         fill(level.begin(), level.end(), -1);
  35.  
  36.         queue<int> q;
  37.         q.push(s);
  38.         level[s] = 0;
  39.  
  40.         while (!q.empty()) {
  41.             int u = q.front();
  42.             q.pop();
  43.  
  44.             for (auto &e : g[u]) {
  45.                 if (e.cap > 0 && level[e.v] == -1) {
  46.                     level[e.v] = level[u] + 1;
  47.                     q.push(e.v);
  48.                 }
  49.             }
  50.         }
  51.  
  52.         return level[t] != -1;
  53.     }
  54.  
  55.     ll dfs(int u, int t, ll pushed) {
  56.         if (u == t || pushed == 0)
  57.             return pushed;
  58.  
  59.         for (int &i = cur[u]; i < (int)g[u].size(); i++) {
  60.             Edge &e = g[u][i];
  61.  
  62.             if (e.cap <= 0 || level[e.v] != level[u] + 1)
  63.                 continue;
  64.  
  65.             ll tr = dfs(e.v, t, min(pushed, e.cap));
  66.  
  67.             if (tr == 0)
  68.                 continue;
  69.  
  70.             e.cap -= tr;
  71.             g[e.v][e.rev].cap += tr;
  72.  
  73.             return tr;
  74.         }
  75.  
  76.         return 0;
  77.     }
  78.  
  79.     ll maxflow(int s, int t) {
  80.         ll ans = 0;
  81.  
  82.         while (bfs(s, t)) {
  83.             fill(cur.begin(), cur.end(), 0);
  84.  
  85.             while (ll pushed = dfs(s, t, INF))
  86.                 ans += pushed;
  87.         }
  88.  
  89.         return ans;
  90.     }
  91. };
  92.  
  93. int main() {
  94.     ios::sync_with_stdio(false);
  95.     cin.tie(nullptr);
  96.  
  97.     int n, k;
  98.     cin >> n >> k;
  99.  
  100.     vector<ll> a(n + 1);
  101.  
  102.     for (int i = 1; i <= n; i++)
  103.         cin >> a[i];
  104.  
  105.     vector<vector<int>> adj(n + 1);
  106.  
  107.     for (int i = 1; i < n; i++) {
  108.         int u, v;
  109.         cin >> u >> v;
  110.  
  111.         adj[u].push_back(v);
  112.         adj[v].push_back(u);
  113.     }
  114.  
  115.     struct Query {
  116.         int u, v;
  117.         ll c;
  118.     };
  119.  
  120.     vector<Query> q(k + 1);
  121.  
  122.     for (int i = 1; i <= k; i++)
  123.         cin >> q[i].u >> q[i].v >> q[i].c;
  124.  
  125.     // Binary lifting
  126.  
  127.     int LOG = 1;
  128.     while ((1 << LOG) <= n)
  129.         LOG++;
  130.  
  131.     vector<vector<int>> up(n + 1, vector<int>(LOG));
  132.     vector<int> depth(n + 1);
  133.  
  134.     // Iterative DFS
  135.  
  136.     vector<int> order;
  137.     order.reserve(n);
  138.  
  139.     order.push_back(1);
  140.     up[1][0] = 1;
  141.  
  142.     for (int i = 0; i < (int)order.size(); i++) {
  143.         int u = order[i];
  144.  
  145.         for (int v : adj[u]) {
  146.             if (v == up[u][0])
  147.                 continue;
  148.  
  149.             up[v][0] = u;
  150.             depth[v] = depth[u] + 1;
  151.  
  152.             order.push_back(v);
  153.         }
  154.     }
  155.  
  156.     for (int j = 1; j < LOG; j++) {
  157.         for (int u = 1; u <= n; u++) {
  158.             up[u][j] = up[up[u][j - 1]][j - 1];
  159.         }
  160.     }
  161.  
  162.     auto lca = [&](int u, int v) {
  163.         if (depth[u] < depth[v])
  164.             swap(u, v);
  165.  
  166.         int d = depth[u] - depth[v];
  167.  
  168.         for (int i = 0; i < LOG; i++) {
  169.             if (d >> i & 1)
  170.                 u = up[u][i];
  171.         }
  172.  
  173.         if (u == v)
  174.             return u;
  175.  
  176.         for (int i = LOG - 1; i >= 0; i--) {
  177.             if (up[u][i] != up[v][i]) {
  178.                 u = up[u][i];
  179.                 v = up[v][i];
  180.             }
  181.         }
  182.  
  183.         return up[u][0];
  184.     };
  185.  
  186.     // Tao node phu (u, i)
  187.  
  188.     vector<vector<int>> id(n + 1, vector<int>(LOG));
  189.  
  190.     int cnt = n;
  191.  
  192.     for (int u = 1; u <= n; u++) {
  193.         id[u][0] = ++cnt;
  194.     }
  195.  
  196.     for (int i = 1; i < LOG; i++) {
  197.         for (int u = 1; u <= n; u++) {
  198.             if (depth[u] + 1 < (1 << i))
  199.                 continue;
  200.  
  201.             id[u][i] = ++cnt;
  202.         }
  203.     }
  204.  
  205.     // Node ngay
  206.  
  207.     vector<int> day(k + 1);
  208.  
  209.     for (int i = 1; i <= k; i++)
  210.         day[i] = ++cnt;
  211.  
  212.     int S = ++cnt;
  213.     int T = ++cnt;
  214.  
  215.     Dinic dinic(cnt);
  216.  
  217.     // Original nodes -> T
  218.  
  219.     for (int u = 1; u <= n; u++)
  220.         dinic.addEdge(u, T, a[u]);
  221.  
  222.     // Auxiliary nodes
  223.  
  224.     for (int u = 1; u <= n; u++) {
  225.         dinic.addEdge(id[u][0], u, INF);
  226.     }
  227.  
  228.     for (int i = 1; i < LOG; i++) {
  229.         for (int u = 1; u <= n; u++) {
  230.             if (!id[u][i])
  231.                 continue;
  232.  
  233.             int mid = up[u][i - 1];
  234.  
  235.             dinic.addEdge(id[u][i], id[u][i - 1], INF);
  236.             dinic.addEdge(id[u][i], id[mid][i - 1], INF);
  237.         }
  238.     }
  239.  
  240.     // Phan ra doan di len tu u, gom len dinh LCA neu can
  241.  
  242.     auto addPath = [&](int d, int u, int len) {
  243.         for (int i = LOG - 1; i >= 0; i--) {
  244.             if (len >> i & 1) {
  245.                 dinic.addEdge(day[d], id[u][i], INF);
  246.  
  247.                 u = up[u][i];
  248.             }
  249.         }
  250.     };
  251.  
  252.     // Source -> day -> auxiliary nodes
  253.  
  254.     for (int i = 1; i <= k; i++) {
  255.         int u = q[i].u;
  256.         int v = q[i].v;
  257.         ll c = q[i].c;
  258.  
  259.         dinic.addEdge(S, day[i], c);
  260.  
  261.         int w = lca(u, v);
  262.  
  263.         // u -> LCA (co lay LCA)
  264.         addPath(i, u, depth[u] - depth[w] + 1);
  265.  
  266.         // v -> LCA (khong lay LCA)
  267.         addPath(i, v, depth[v] - depth[w]);
  268.     }
  269.  
  270.     cout << dinic.maxflow(S, T) << '\n';
  271.  
  272.     return 0;
  273. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
4 2
0 1 2 2
1 4
2 4
3 4
1 2 2
1 3 3
stdout
copy 
5
https://ideone.com/vbXij6
language:
C++14 (gcc 8.3)
created:
49 minutes 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!