Hướng giải của Đường về nguồn cộ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

Nhận xét

Bài toán yêu cầu tính tổng giá trị trên đường đi từ gốc đến một đỉnh, kèm cập nhật giá trị đỉnh. Khi giá trị của đỉnh \(u\) thay đổi, nó ảnh hưởng đến tổng đường đi của tất cả đỉnh trong subtree của \(u\).

Ý tưởng giải

Sử dụng Euler Tour Type 2 (entry + exit) kết hợp với BIT dạng mảng hiệu:

  1. Euler Tour Type 2: DFS ghi \(tin[u]\) (vào) và \(tout[u]\) (ra). Mỗi đỉnh xuất hiện 2 lần.
  2. Cập nhật: Khi giá trị đỉnh \(u\) thay đổi một lượng \(delta\), ta cộng \(delta\) vào đoạn \([tin[u], tout[u]]\) trên BIT (vì mọi đỉnh trong subtree của \(u\) đều có đường đi từ gốc đi qua \(u\)).
  3. Truy vấn: Tổng từ gốc đến \(u\) = tổng tiền tố tại vị trí \(tin[u]\) trên BIT.

Đây là kỹ thuật tương tự bài "Cập nhật subtree - truy vấn điểm" nhưng áp dụng cho bài toán đường đi gốc.

Độ phức tạp

  • Tiền xử lý DFS: \(O(N)\)
  • Mỗi truy vấn cập nhật: \(O(\log N)\)
  • Mỗi truy vấn tổng: \(O(\log N)\)
  • Tổng: \(O((N + Q) \log N)\)

Code mẫu

// Giải thuật ett cho bài toán ett-root-sum\n#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 200005;
vector<int> adj[MAXN];
int tin[MAXN], tout[MAXN];
ll val[MAXN];
ll bit[2 * MAXN];
int timer_dfs = 0;
int n, q;

void bit_update(int i, ll delta) {
    for (; i <= 2 * n; i += i & (-i))
        bit[i] += delta;
}

ll bit_query(int i) {
    ll sum = 0;
    for (; i > 0; i -= i & (-i))
        sum += bit[i];
    return sum;
}

void dfs(int u, int parent) {
    tin[u] = ++timer_dfs;
    for (int v : adj[u]) {
        if (v != parent) {
            dfs(v, u);
        }
    }
    tout[u] = ++timer_dfs;
}

int main() {
    // Doc du lieu dau vao
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> 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, 0);

    // Khoi tao: khi dat gia tri val[i] cho dinh i,
    // no anh huong den tat ca dinh trong subtree cua i
    for (int i = 1; i <= n; i++) {
        bit_update(tin[i], val[i]);
        bit_update(tout[i] + 1, -val[i]);
    }

    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int u;
            ll new_val;
            cin >> u >> new_val;
            ll delta = new_val - val[u];
            val[u] = new_val;
            // Cap nhat subtree: cong delta len doan [tin[u], tout[u]]
            bit_update(tin[u], delta);
            bit_update(tout[u] + 1, -delta);
        } else {
            int u;
            cin >> u;
            // Tong tu goc den u = prefix sum tai tin[u]
            cout << bit_query(tin[u]) << "\n";
        }
    }
    return 0;
}

Nhận xét

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