Hướng giải của Cộng đường đi

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Lời giải cho Cộng đường đi

Thuật toán

Dùng Heavy Light Decomposition để phân tách cây thành các chuỗi, mỗi truy vấn xử lý trong \(O(log^2 N)\).

Kết hợp HLD với Fenwick Tree (BIT) để cập nhật đoạn và truy vấn điểm.

Cách tiếp cận:

  • Cập nhật đường đi \(u \to v\): tương tự path query nhưng thay vì đọc giá trị, ta cộng \(val\) vào đoạn trên BIT.
  • Truy vấn điểm \(u\): chỉ cần đọc giá trị tại \(pos[u]\) trên BIT.

BIT hỗ trợ cộng đoạn và truy vấn điểm trong \(O(\log N)\).

Độ phức tạp

\(O((N + Q) \log^2 N)\) cho cập nhật, \(O((N + Q) \log N)\) cho truy vấn.

Hướng dẫn giải

Sử dụng thuật toán phù hợp để giải quyết bài toán.

Mã nguồn C++

// Giải thuật hld cho bài toán hld-path-add\n#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 100005;

int n, q;
vector<int> adj[MAXN];
int parent[MAXN], depth[MAXN], sz[MAXN], heavy[MAXN];
int head[MAXN], pos[MAXN], cur_pos;
ll init_val[MAXN], bit[MAXN];

void dfs(int u, int p) {
    parent[u] = p;
    sz[u] = 1;
    heavy[u] = -1;
    int max_sz = 0;
    for (int v : adj[u]) {
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        dfs(v, u);
        sz[u] += sz[v];
        if (sz[v] > max_sz) {
            max_sz = sz[v];
            heavy[u] = v;
        }
    }
}

void decompose(int u, int h) {
    head[u] = h;
    pos[u] = cur_pos++;
    if (heavy[u] != -1)
        decompose(heavy[u], h);
    for (int v : adj[u]) {
        if (v == parent[u] || v == heavy[u]) continue;
        decompose(v, v);
    }
}

void bit_add(int idx, ll val) {
    for (int i = idx; i <= n; i += i & -i)
        bit[i] += val;
}

ll bit_sum(int idx) {
    ll res = 0;
    for (int i = idx; i > 0; i -= i & -i)
        res += bit[i];
    return res;
}

void range_add(int l, int r, ll val) {
    bit_add(l, val);
    bit_add(r + 1, -val);
}

void path_add(int u, int v, ll val) {
    while (head[u] != head[v]) {
        if (depth[head[u]] > depth[head[v]]) swap(u, v);
        range_add(pos[head[v]] + 1, pos[v] + 1, val);
        v = parent[head[v]];
    }
    if (depth[u] > depth[v]) swap(u, v);
    range_add(pos[u] + 1, pos[v] + 1, val);
}

int main() {
    // Doc du lieu dau vao
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> init_val[i];
    for (int i = 0; i < n-1; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, -1);
    cur_pos = 0;
    decompose(1, 1);
    for (int i = 1; i <= n; i++) {
        bit_add(i, init_val[i]);
        bit_add(i + 1, -init_val[i]);
    }
    while (q--) {
        int type; cin >> type;
        if (type == 1) {
            int u, v; ll val; cin >> u >> v >> val;
            path_add(u, v, val);
        } else {
            int u; cin >> u;
            cout << bit_sum(pos[u] + 1) << '\n';
        }
    }
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.