Advertisement
Guest User

Untitled

a guest
Feb 11th, 2023
216
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.58 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int nax = 4e5 + 10;
  5.  
  6. #define all(x) begin(x), end(x)
  7.  
  8. struct HLD {
  9.     int n;
  10.     std::vector<int> siz, top, dep, parent, in, out, seq;
  11.     std::vector<std::vector<int>> adj;
  12.     HLD(int n) : n(n), siz(n), top(n), dep(n), parent(n, -1), in(n), out(n), seq(n), adj(n) {}
  13.     void addEdge(int u, int v) {
  14.         adj[u].push_back(v);
  15.         adj[v].push_back(u);
  16.     }
  17.     void init(int root = 0) {
  18.         top[root] = root;
  19.         dfs1(root);
  20.         dfs2(root);
  21.     }
  22.     void dfs1(int u) {
  23.         if (parent[u] != -1) {
  24.             adj[u].erase(std::find(adj[u].begin(), adj[u].end(), parent[u]));
  25.         }
  26.  
  27.         siz[u] = 1;
  28.         for (auto &v : adj[u]) {
  29.             parent[v] = u;
  30.             dep[v] = dep[u] + 1;
  31.             dfs1(v);
  32.             siz[u] += siz[v];
  33.             if (siz[v] > siz[adj[u][0]]) {
  34.                 std::swap(v, adj[u][0]);
  35.             }
  36.         }
  37.     }
  38.     int cur = 0;
  39.     void dfs2(int u) {
  40.         in[u] = cur++;
  41.         seq[in[u]] = u;
  42.         for (auto v : adj[u]) {
  43.             top[v] = v == adj[u][0] ? top[u] : v;
  44.             dfs2(v);
  45.         }
  46.         out[u] = cur;
  47.     }
  48.     int lca(int u, int v) {
  49.         while (top[u] != top[v]) {
  50.             if (dep[top[u]] > dep[top[v]]) {
  51.                 u = parent[top[u]];
  52.             } else {
  53.                 v = parent[top[v]];
  54.             }
  55.         }
  56.         return dep[u] < dep[v] ? u : v;
  57.     }
  58. };
  59.  
  60. struct Fenwick {
  61.     int64_t bit[nax];
  62.     void add(int i, int64_t v) {
  63.         assert(i < nax);
  64.         for (; i < nax ; i += i & -i) bit[i] += v;
  65.     }
  66.     int64_t get(int i) {
  67.         int64_t res = 0;
  68.         assert(i >= 0);
  69.         for (; i > 0 ; i -= i & -i) res += bit[i];
  70.         return res;
  71.     }
  72.     int64_t get(int l, int r) {
  73.         return get(r) - get(l - 1);
  74.     }
  75.  
  76.     void reset() {
  77.         memset(bit, 0, sizeof(bit));
  78.     }
  79. };
  80. int n, q;
  81. array <int, 5> e[nax];
  82. int l[nax], r[nax];
  83. array <int64_t, 3> query[nax];
  84. int check[nax];
  85. int ans[nax];
  86. Fenwick sum;
  87. Fenwick rm;
  88.  
  89.  
  90.  
  91.  
  92. int main() {
  93.     cin.tie(0)->sync_with_stdio(false);
  94.  
  95.     cin >> n;
  96.     HLD hld(n);
  97.  
  98.     for (int i = 1 ; i < n ; ++ i) {
  99.         auto &[u, v, w, c, s] = e[i];
  100.         cin >> u >> v >> w >> c >> s;
  101.         -- u, -- v;
  102.         hld.addEdge(u, v);
  103.     }
  104.     hld.init();
  105.  
  106.     auto update_edge = [&](int u, int v, int64_t w, Fenwick &F) {
  107.         if (hld.siz[u] > hld.siz[v]) swap(u, v);
  108.         F.add(hld.in[u], w);
  109.         F.add(hld.out[u], -w);
  110.     };
  111.  
  112.     auto sum_root = [&](int u, Fenwick &F) -> int64_t {
  113.         return F.get(hld.in[u]);
  114.     };
  115.  
  116.     auto query_path = [&](int u, int v, Fenwick &F) -> int64_t {
  117.         int lc = hld.lca(u, v);
  118.         return sum_root(u, F) + sum_root(v, F) - 2 * sum_root(lc, F);
  119.     };
  120.  
  121.  
  122.     cin >> q;
  123.  
  124.     for (int i = 1 ; i <= q ; ++ i) {
  125.         auto &[a, b, e] = query[i];
  126.         cin >> a >> b >> e;
  127.         -- a, -- b;
  128.         l[i] = 0, r[i] = 1e9;
  129.     }
  130.  
  131.  
  132.     while (true) {
  133.         bool ok = true;
  134.         vector <array <int64_t, 2>> query_event;
  135.  
  136.         for (int i = 1 ; i <= q ; ++ i) {
  137.             check[i] = (r[i] + l[i]) >> 1;
  138.             if (l[i] <= r[i]) {
  139.                 query_event.push_back({check[i], i});
  140.             }
  141.             ok &= l[i] > r[i];
  142.         }
  143.  
  144.         if (ok) break;
  145.         vector <array <int64_t, 3>> events;
  146.         sum.reset(), rm.reset();
  147.         for (int i = 1 ; i < n ; ++ i) {
  148.             auto &[u, v, w, c, s] = e[i];
  149.             events.push_back({w, -1, i});
  150.             events.push_back({s, 1, i});
  151.         }
  152.         int top_event = 0;
  153.  
  154.         sort(all(query_event));
  155.         sort(all(events));
  156.  
  157.  
  158.         for (auto [ck, id] : query_event) {
  159.             auto [u, v, tot] = query[id];
  160.  
  161.             while (top_event < events.size() && events[top_event][0] < ck) {
  162.                 auto [W, typ, i] = events[top_event++];
  163.                 auto &[u, v, w, c, s] = e[i];
  164.  
  165.                 if (typ == -1) {
  166.                     update_edge(u, v, c, sum);
  167.                 } else {
  168.                     update_edge(u, v, -c, sum);
  169.                     update_edge(u, v, 1, rm);
  170.                 }
  171.             }
  172.             bool ok = true;
  173.             ok &= query_path(u, v, rm) == 0;
  174.             ok &= query_path(u, v, sum) <= tot;
  175.             if (ok) {
  176.                 ans[id] = check[id];
  177.                 l[id] = check[id] + 1;
  178.             } else {
  179.                 r[id] = check[id] - 1;
  180.             }
  181.         }
  182.     }
  183.  
  184.     for (int i = 1 ; i <= q ; ++ i) {
  185.         cout << ans[i] << '\n';
  186.     }
  187.  
  188.  
  189. }
  190.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement