Hướng dẫn giải của [CSES 1137] Subtree Queries

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Hãy xây dựng một Euler tour của cây. Mỗi cây con tương ứng với một đoạn liên tiếp trong thứ tự duyệt, do đó ta có thể trả lời các truy vấn một cách hiệu quả bằng một cây phân đoạn (segment tree).

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

const int N = 200001;
int v[N];
vector<int> g[N];
int tour_in[N], tour_out[N], tour_index;

void dfs(int node, int parent) {
    tour_in[node] = ++tour_index;
    for (int child : g[node]) {
        if (child == parent) continue;
        dfs(child, node);
    }
    tour_out[node] = tour_index;
}

const int TREE_SIZE = 1 << 18;
ll tree[TREE_SIZE * 2];

// Thay đổi giá trị tại vị trí k thành x.
void change(int k, int x) {
    k += TREE_SIZE;
    tree[k] = x;
    while (k > 1) {
        k /= 2;
        tree[k] = tree[2 * k] + tree[2 * k + 1];
    }
}

// Trả về tổng các giá trị trong đoạn [l, r].
ll query(int l, int r) {
    l += TREE_SIZE;
    r += TREE_SIZE;
    ll sum = 0;
    while (l <= r) {
        if (l % 2 == 1) sum += tree[l++];
        if (r % 2 == 0) sum += tree[r--];
        l /= 2;
        r /= 2;
    }
    return sum;
}

int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1, -1);
    for (int i = 1; i <= n; i++) {
        change(tour_in[i], v[i]);
    }
    for (int i = 1; i <= q; i++) {
        int t, s;
        cin >> t >> s;
        if (t == 1) {
            int x;
            cin >> x;
            change(tour_in[s], x);
        } else {
            cout << query(tour_in[s], tour_out[s]) << '\n';
        }
    }
}
Tài liệu tham khảo về kỹ thuật Euler tour

Chương trình tham khảo

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

const int N = 200001;
int v[N];
vector<int> g[N];
int tour_in[N], tour_out[N], tour_index;

void dfs(int node, int parent) {
    tour_in[node] = ++tour_index;
    for (int child : g[node]) {
        if (child == parent) continue;
        dfs(child, node);
    }
    tour_out[node] = tour_index;
}

const int TREE_SIZE = 1 << 18;
ll tree[TREE_SIZE * 2];

// Changes the value in position k to x.
void change(int k, int x) {
    k += TREE_SIZE;
    tree[k] = x;
    while (k > 1) {
        k /= 2;
        tree[k] = tree[2 * k] + tree[2 * k + 1];
    }
}

// Returns the sum of values in range [l, r].
ll query(int l, int r) {
    l += TREE_SIZE;
    r += TREE_SIZE;
    ll sum = 0;
    while (l <= r) {
        if (l % 2 == 1) sum += tree[l++];
        if (r % 2 == 0) sum += tree[r--];
        l /= 2;
        r /= 2;
    }
    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1, -1);
    for (int i = 1; i <= n; i++) {
        change(tour_in[i], v[i]);
    }
    for (int i = 1; i <= q; i++) {
        int t, s;
        cin >> t >> s;
        if (t == 1) {
            int x;
            cin >> x;
            change(tour_in[s], x);
        } else {
            cout << query(tour_in[s], tour_out[s]) << '\n';
        }
    }
}

Bình luận

Hãy đọc nội quy trước khi bình luận.

Không có bình luận tại thời điểm này.