Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- const int nax = 4e5 + 10;
- #define all(x) begin(x), end(x)
- struct HLD {
- int n;
- std::vector<int> siz, top, dep, parent, in, out, seq;
- std::vector<std::vector<int>> adj;
- HLD(int n) : n(n), siz(n), top(n), dep(n), parent(n, -1), in(n), out(n), seq(n), adj(n) {}
- void addEdge(int u, int v) {
- adj[u].push_back(v);
- adj[v].push_back(u);
- }
- void init(int root = 0) {
- top[root] = root;
- dfs1(root);
- dfs2(root);
- }
- void dfs1(int u) {
- if (parent[u] != -1) {
- adj[u].erase(std::find(adj[u].begin(), adj[u].end(), parent[u]));
- }
- siz[u] = 1;
- for (auto &v : adj[u]) {
- parent[v] = u;
- dep[v] = dep[u] + 1;
- dfs1(v);
- siz[u] += siz[v];
- if (siz[v] > siz[adj[u][0]]) {
- std::swap(v, adj[u][0]);
- }
- }
- }
- int cur = 0;
- void dfs2(int u) {
- in[u] = cur++;
- seq[in[u]] = u;
- for (auto v : adj[u]) {
- top[v] = v == adj[u][0] ? top[u] : v;
- dfs2(v);
- }
- out[u] = cur;
- }
- int lca(int u, int v) {
- while (top[u] != top[v]) {
- if (dep[top[u]] > dep[top[v]]) {
- u = parent[top[u]];
- } else {
- v = parent[top[v]];
- }
- }
- return dep[u] < dep[v] ? u : v;
- }
- };
- struct Fenwick {
- int64_t bit[nax];
- void add(int i, int64_t v) {
- assert(i < nax);
- for (; i < nax ; i += i & -i) bit[i] += v;
- }
- int64_t get(int i) {
- int64_t res = 0;
- assert(i >= 0);
- for (; i > 0 ; i -= i & -i) res += bit[i];
- return res;
- }
- int64_t get(int l, int r) {
- return get(r) - get(l - 1);
- }
- void reset() {
- memset(bit, 0, sizeof(bit));
- }
- };
- int n, q;
- array <int, 5> e[nax];
- int l[nax], r[nax];
- array <int64_t, 3> query[nax];
- int check[nax];
- int ans[nax];
- Fenwick sum;
- Fenwick rm;
- int main() {
- cin.tie(0)->sync_with_stdio(false);
- cin >> n;
- HLD hld(n);
- for (int i = 1 ; i < n ; ++ i) {
- auto &[u, v, w, c, s] = e[i];
- cin >> u >> v >> w >> c >> s;
- -- u, -- v;
- hld.addEdge(u, v);
- }
- hld.init();
- auto update_edge = [&](int u, int v, int64_t w, Fenwick &F) {
- if (hld.siz[u] > hld.siz[v]) swap(u, v);
- F.add(hld.in[u], w);
- F.add(hld.out[u], -w);
- };
- auto sum_root = [&](int u, Fenwick &F) -> int64_t {
- return F.get(hld.in[u]);
- };
- auto query_path = [&](int u, int v, Fenwick &F) -> int64_t {
- int lc = hld.lca(u, v);
- return sum_root(u, F) + sum_root(v, F) - 2 * sum_root(lc, F);
- };
- cin >> q;
- for (int i = 1 ; i <= q ; ++ i) {
- auto &[a, b, e] = query[i];
- cin >> a >> b >> e;
- -- a, -- b;
- l[i] = 0, r[i] = 1e9;
- }
- while (true) {
- bool ok = true;
- vector <array <int64_t, 2>> query_event;
- for (int i = 1 ; i <= q ; ++ i) {
- check[i] = (r[i] + l[i]) >> 1;
- if (l[i] <= r[i]) {
- query_event.push_back({check[i], i});
- }
- ok &= l[i] > r[i];
- }
- if (ok) break;
- vector <array <int64_t, 3>> events;
- sum.reset(), rm.reset();
- for (int i = 1 ; i < n ; ++ i) {
- auto &[u, v, w, c, s] = e[i];
- events.push_back({w, -1, i});
- events.push_back({s, 1, i});
- }
- int top_event = 0;
- sort(all(query_event));
- sort(all(events));
- for (auto [ck, id] : query_event) {
- auto [u, v, tot] = query[id];
- while (top_event < events.size() && events[top_event][0] < ck) {
- auto [W, typ, i] = events[top_event++];
- auto &[u, v, w, c, s] = e[i];
- if (typ == -1) {
- update_edge(u, v, c, sum);
- } else {
- update_edge(u, v, -c, sum);
- update_edge(u, v, 1, rm);
- }
- }
- bool ok = true;
- ok &= query_path(u, v, rm) == 0;
- ok &= query_path(u, v, sum) <= tot;
- if (ok) {
- ans[id] = check[id];
- l[id] = check[id] + 1;
- } else {
- r[id] = check[id] - 1;
- }
- }
- }
- for (int i = 1 ; i <= q ; ++ i) {
- cout << ans[i] << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement