Notes: ABC 133F

Правка en2, от NeoYL, 2023-12-11 19:07:37

I'm writing this blog just to record down some personal notes for solved problems:

ABC 133F : segment tree to solve tree problem

First of all, we can observe that queries can be done offline and the only thing that matters for each query is the color.

Lets do each color one by one, we can observe that distance between two nodes in the query = original distance & mdash; sum of edge weight of color $$$x$$$ + number of edges that have color $$$x$$$ in the path.

Now let us try to find what can be done.We can see that the number of edges with color $$$x$$$ going out of subtree $$$u$$$ will $$$ + 1$$$ if the starting point is from subtree $$$u$$$.So we can just $$$ + 1$$$ to all nodes inside subtree $$$u$$$.Then we can see that number of edges from node $$$x$$$ to $$$y$$$.Similarly, we can do $$$ + W$$$ for weight sum.

distance in original graph, edge number and weight sum in the path can be found in $$$O(N log N)$$$ using binary lifting and a dfs function.

This reduces the problem to $$$O(N ^ 2)$$$, lets optimize it!

We can try finding a better way to do the $$$ + 1$$$ and $$$ + W$$$ operations.Well, if you have learnt dfn, you should be able to continue from here.If we represent $$$tin_{ i }$$$ be the time we entered subtree $$$i$$$ and $$$tout_{ i }$$$ we left subtree $$$i$$$.Then we can use this to observe that we need to do $$$ + val$$$ in a range and find a value at a point $$$p$$$. * Yes, segment tree!*

However, we cannot just declare a new segment tree each time.We need to reuse the segment tree.So, we'll have to do $$$-1$$$ and $$$-W$$$ operations to revert the segment tree, or do something like range set.

Code: ~~~~~ // Problem: F — Colorful Tree // Memory Limit: 1024 MB // Time Limit: 4000 ms

//闲敲棋子落灯花//

include<bits/stdc++.h>

using namespace std; using i64 = long long;

struct edge { int u, v, color, w; }; struct query { int u, v, color, new_w, id; }; const int N = 1e5 + 50, K = 30; vector<pair<int, int>> G[N]; int dep[N], sp[N][K], val[N], ti, tin[N], tout[N]; void dfs(int u, int p) { tin[u] = ++ti; dep[u] = dep[p] + 1; sp[u][0] = p; for (int i = 1; i < K; i++)sp[u][i] = sp[sp[u][i — 1]][i — 1]; for (auto v : G[u]) if (v.first != p) { val[v.first] = val[u] + v.second; dfs(v.first, u); } tout[u] = ti; } int lca(int u, int v) { if (dep[u] < dep[v]) swap(u, v); for (int i = K — 1; i >= 0; i--)if (dep[sp[u][i]] >= dep[v])u = sp[u][i]; if (u == v) return u; for (int i = K — 1; i >= 0; i--)if (sp[u][i] != sp[v][i])u = sp[u][i], v = sp[v][i]; return sp[v][0]; } int dis(int u, int v) { int l = lca(u, v); return val[u] + val[v] — 2 * val[l]; } struct segtree { struct node { i64 v; friend node operator + (node a, node b) { node t; t.v = a.v + b.v; return t; } }; vector tr; vector tag; int SZ = 0; void apply_node(int p, int x) { tr[p].v += x; tag[p] += x; } void pushdown(int p) { if (tag[p] != 0) { apply_node(p << 1, tag[p]); apply_node(p << 1 | 1, tag[p]); tag[p] = 0; } return; } segtree(int N) { SZ = N + 200; tr.resize(SZ * 4); tag.assign(SZ * 4, 0); } #define ls p<<1 #define rs p<<1|1 void update(int x, int v) { update(1, 1, SZ — 100, v, x, x); } void update(int x, int y, int v) { update(1, 1, SZ — 100, v, x, y); } void update(int p, int l, int r, int v, int lq, int rq) { //cout << "updating: " << p << ' ' << l << ' ' << r << ' ' << lq << ' ' << rq <<" with value: "<<v<< '\n'; if (lq <= l && r <= rq) { apply_node(p, v); return; } int mid = (l + r) >> 1; pushdown(p); if (lq <= mid) update(ls, l, mid, v, lq, rq); if (rq >= mid + 1) update(rs, mid + 1, r, v, lq, rq); tr[p] = tr[ls] + tr[rs]; } node query(int x) { return query(1, 1, SZ — 100, x, x); } node query(int x, int y) { return query(1, 1, SZ — 100, x, y); } node query(int p, int l, int r, int lq, int rq) { //cout << "querying: " << p << ' ' << l << ' ' << r << ' ' << lq << ' ' << rq << '\n'; if (lq <= l && r <= rq) { return tr[p]; } int mid = (l + r) >> 1; pushdown(p); if (lq <= mid && rq >= mid + 1) return query(ls, l, mid, lq, rq) + query(rs, mid + 1, r, lq, rq); if (lq <= mid) return query(ls, l, mid, lq, rq); if (rq >= mid + 1) return query(rs, mid + 1, r, lq, rq); } }; //update/query -> point or range int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

int N, Q; cin >> N >> Q;
vector<vector<edge>> C(N + 1);
for (int i = 0; i < N - 1; i++) {
    int a, b, c, d; cin >> a >> b >> c >> d;
    G[a].push_back({ b,d });
    G[b].push_back({ a,d }); //original graph
    C[c].push_back({ a,b,c,d }); //push into the edge set with color c
}
dfs(1, 0);
vector<vector<query>> Qp(N + 1);
vector<int> ans(Q + 1);
for (int i = 0; i < Q; i++) {
    int a, b, c, d; cin >> a >> b >> c >> d;
    ans[i] = dis(c, d);
    Qp[a].push_back({ c,d,a,b,i });
}
segtree segcnt(N), segval(N); // two segment trees, one countring the number of edges and the other counting the sum of weights
for (int i = 1; i <= N; i++) {
    for (auto p : C[i]) { // for each edge that has the color i
        int u = p.u, v = p.v, w = p.w;
        if (dep[u] > dep[v]) swap(u, v);//make sure we swap to do the +1 operation in the son not the parent
        segcnt.update(tin[v], tout[v], 1);
        segval.update(tin[v], tout[v], w);
    }

    for (auto p : Qp[i]) { // for each query that has color i
        int u = p.u, v = p.v, w = p.new_w;
        if (dep[u] > dep[v]) swap(u, v);
        int l = lca(u, v);
        int cnt = segcnt.query(tin[u]).v + segcnt.query(tin[v]).v - 2 * segcnt.query(tin[l]).v;
        int val = segval.query(tin[u]).v + segval.query(tin[v]).v - 2 * segval.query(tin[l]).v;
        ans[p.id] -= val;
        ans[p.id] += cnt * p.new_w;
    }

    for (auto p : C[i]) {
        int u = p.u, v = p.v, w = p.w;
        if (dep[u] > dep[v]) swap(u, v);
        segcnt.update(tin[v], tout[v], -1);
        segval.update(tin[v], tout[v], -w);
    }
}
for (int i = 0; i < Q; i++) {
    cout << ans[i] << '\n';
}

} ~~~~~

Теги tree, segment tree, weighted graph, counting

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en30 Английский NeoYL 2023-12-31 12:37:32 7
en29 Английский NeoYL 2023-12-14 19:34:13 18
en28 Английский NeoYL 2023-12-14 19:32:15 348
en27 Английский NeoYL 2023-12-14 19:26:45 17 Tiny change: '\n<spoiler> \n```cpp' -> '\n<spoiler summary="Code"> \n```cpp'
en26 Английский NeoYL 2023-12-14 19:26:18 5298
en25 Английский NeoYL 2023-12-14 17:59:14 5 Tiny change: 'timization">\nWe can' -> 'timization used">\nWe can'
en24 Английский NeoYL 2023-12-14 13:29:32 12 Tiny change: ' summary="Half solution"' -> ' summary="Incomplete solution"'
en23 Английский NeoYL 2023-12-14 08:58:57 215
en22 Английский NeoYL 2023-12-14 08:57:58 141 Tiny change: ' summary="$O(N^2)$ s' -> ' summary=" $O(N^2)$ s'
en21 Английский NeoYL 2023-12-13 13:27:55 15
en20 Английский NeoYL 2023-12-12 13:33:13 4
en19 Английский NeoYL 2023-12-12 09:13:23 2 Tiny change: 'ed to add +1 to each n' -> 'ed to add $+1$ to each n'
en18 Английский NeoYL 2023-12-12 05:48:22 2 Tiny change: 'round 2400 ish proble' -> 'round 2400-ish proble'
en17 Английский NeoYL 2023-12-12 04:44:37 8
en16 Английский NeoYL 2023-12-12 03:55:24 86
en15 Английский NeoYL 2023-12-12 03:47:05 36 Tiny change: 'n problems, which ar' -> 'n problems (normally around 2300 ish problems), which ar'
en14 Английский NeoYL 2023-12-12 03:46:04 16
en13 Английский NeoYL 2023-12-12 03:45:29 20 Tiny change: 'note 2), an upvote would be ' -> 'note 2), a significant upvote from you would be '
en12 Английский NeoYL 2023-12-12 03:42:52 160
en11 Английский NeoYL 2023-12-12 03:38:43 22
en10 Английский NeoYL 2023-12-12 03:37:41 324
en9 Английский NeoYL 2023-12-11 19:35:45 4 Tiny change: 'at a point $p$. What do ' -> 'at a point. What do '
en8 Английский NeoYL 2023-12-11 19:34:44 19 Tiny change: 'e able to continue from here' -> 'e able to solve the problem from here'
en7 Английский NeoYL 2023-12-11 19:27:44 64
en6 Английский NeoYL 2023-12-11 19:26:56 40 Tiny change: 'e set.\n\n[AC co' -> 'e set.\n\nThis allows an $O(N log N)$ solution\n\n[AC co'
en5 Английский NeoYL 2023-12-11 19:26:07 20 Tiny change: 'n the path.\n\nNow' -> 'n the path * new weight length.\n\nNow'
en4 Английский NeoYL 2023-12-11 19:25:11 262
en3 Английский NeoYL 2023-12-11 19:23:21 8421 (published)
en2 Английский NeoYL 2023-12-11 19:07:37 7364
en1 Английский NeoYL 2023-12-11 19:00:00 1500 Initial revision (saved to drafts)