Hướng giải của Phát lương

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 cập nhật toàn bộ subtree và truy vấn giá trị tại một đỉnh. Đây là bài toán ngược với truy vấn tổng subtree: thay vì cập nhật điểm và truy vấn đoạn, ta cập nhật đoạn và truy vấn điểm.

Ý tưởng giải

Sử dụng Euler Tour Type 2 (mỗi đỉnh xuất hiện 2 lần: entry và exit) kết hợp với mảng hiệu (difference array) trên BIT:

  1. Euler Tour Type 2: DFS ghi \(tin[u]\) khi vào và \(tout[u]\) khi ra. Mỗi đỉnh xuất hiện 2 lần, tổng số phần tử là \(2N\).
  2. Mảng hiệu: Khi cập nhật subtree của \(u\) với giá trị \(val\):
    • Cộng \(val\) tại vị trí \(tin[u]\)
    • Trừ \(val\) tại vị trí \(tout[u] + 1\)
  3. Truy vấn điểm: Lấy tổng tiền tố tại vị trí \(tin[u]\).
  4. Tính đúng đắn: Mọi vị trí trong đoạn \([tin[u], tout[u]]\) đều nhận được \(+val\), các vị trí ngoài đoạn thì hiệu triệt tiêu.

Độ phức tạp

  • Tiền xử lý: \(O(N)\) cho DFS
  • Cập nhật subtree: \(O(\log N)\) (2 lần update BIT)
  • Truy vấn điểm: \(O(\log N)\) (1 lần query BIT)
  • Tổng: \(O((N + Q) \log N)\)

Code mẫu

// Giải thuật ett cho bài toán ett-subtree-up\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 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;
}

// Cap nhat subtree: cong val len doan [tin[u], tout[u]]
void update_subtree(int u, ll val) {
    bit_update(tin[u], val);
    bit_update(tout[u] + 1, -val);
}

// Truy van gia tri tai dinh u
ll point_query(int u) {
    return bit_query(tin[u]);
}

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

    cin >> n >> q;

    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 gia tri ban dau
    for (int i = 1; i <= n; i++) {
        ll val;
        cin >> val;
        update_subtree(i, val);
    }

    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int u;
            ll val;
            cin >> u >> val;
            update_subtree(u, val);
        } else {
            int u;
            cin >> u;
            cout << point_query(u) << "\n";
        }
    }
    return 0;
}

Nhận xét

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