Hướng dẫn cho Series ℍ𝔾𝔹ℂ𝕡𝕡_'s - 2026 - Contest #3 - The Last Legacy

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: p2o2HuaGiaBao

Tóm tắt đề bài

Cho một cây gồm \(n\) đỉnh (phòng) và \(n-1\) cạnh có trọng số dương (hành lang). Ban đầu, giá trị năng lượng \(a_i\) của mỗi đỉnh đều bằng \(0\). Có \(q\) truy vấn gồm hai loại:

1 x y: Gán lại giá trị năng lượng của đỉnh \(x\) thành \(y\).
2 x: Tính tổng ảnh hưởng tại đỉnh \(x\), tức là tính giá trị:

\[ \sum_{i=1}^{n} a_i \cdot dist(x, i) \]

Giới hạn: \(1 \le n, q \le 10^6\), trọng số cạnh \(w \le 10^6\). Giá trị kết quả có thể rất lớn và cần dùng kiểu dữ liệu lớn hơn 64-bit (ví dụ __int128).

Phân tích

Đây là một bài toán cấu trúc dữ liệu trên cây đòi hỏi tốc độ xử lý rất cao do \(n, q \le 10^6\).
Khoảng cách giữa hai đỉnh \(x\) và \(i\) trên cây được tính bởi công thức:

\[ dist(x, i) = dist(1, x) + dist(1, i) - 2 \cdot dist(1, LCP(x, i)) \]

(với gốc cây là đỉnh \(1\)).
Khi thay đổi năng lượng của một đỉnh \(x\) từ giá trị cũ sang giá trị mới, ta chỉ quan tâm đến độ thay đổi \(\Delta a_x = y - a_x\).
Biến đổi tổng ảnh hưởng tại đỉnh \(x\):

\[ \sum_{i=1}^{n} a_i \cdot dist(x, i) = \sum_{i=1}^{n} a_i \left( dist(1, x) + dist(1, i) - 2 \cdot dist(1, LCP(x, i)) \right) \]

\[ = dist(1, x) \sum_{i=1}^{n} a_i + \sum_{i=1}^{n} a_i \cdot dist(1, i) - 2 \sum_{i=1}^{n} a_i \cdot dist(1, LCP(x, i)) \]
Để quản lý các truy vấn trên cây hiệu quả, ta sử dụng Heavy-Light Decomposition (HLD) kết hợp với Binary Indexed Tree (BIT) (cây Fenwick) trên thứ tự duyệt DFS/HLD.
Tổng trên đường đi từ gốc đến một đỉnh \(x\) được chia thành các đoạn trên các Heavy Path. Trên mỗi đoạn, khoảng cách từ gốc \(1\) đến một nút được biểu diễn tuyến tính qua vị trí trong HLD. Cụ thể, ta cần duy trì hai cây BIT:
- bit1: Quản lý giá trị thay đổi \(\Delta a_i\).
- bit2: Quản lý giá trị \(-\Delta a_i \cdot p[l-1]\) hoặc \(\Delta a_i \cdot p[r]\) tương ứng với trọng số đường đi tích lũy \(p\) trên các đoạn HLD.

Hướng giải quyết (Tối ưu)

Tiền xử lý cây:
- Thực hiện BFS/DFS để tính độ sâu, khoảng cách từ gốc \(dist[u]\), kích thước cây con \(sz[u]\), đỉnh nặng \(heavy[u]\), và cha của mỗi đỉnh.
- Phân rã cây thành các chuỗi nặng nhẹ (HLD) để mỗi đường đi từ đỉnh \(x\) lên gốc được chia thành tối đa \(\log n\) đoạn liên tiếp trên mảng tuyến tính.
- Xây dựng mảng \(p\) lưu trữ khoảng cách tích lũy dọc theo các vị trí HLD (revpos).
Cập nhật (1 x y):
- Tính phần thay đổi \(\text{res} = y - a_x\). Nếu \(\text{res} = 0\) thì bỏ qua.
- Cập nhật giá trị \(a_x = y\), đồng thời cập nhật vào các cấu trúc BIT trên tất cả các đoạn HLD từ \(x\) đi ngược lên gốc.
Truy vấn (2 x):
- Đi ngược từ \(x\) lên gốc theo các đoạn HLD. Tại mỗi đoạn từ \(top\) đến \(curr\), sử dụng hai cây BIT để tính nhanh tổng trọng số ảnh hưởng theo công thức phân rã đoạn.
- Kết quả cuối cùng thu được bằng cách tổng hợp các giá trị trên tất cả các đoạn HLD từ \(x\) lên gốc, sử dụng kiểu dữ liệu __int128 để tránh tràn số.

Độ phức tạp

Thời gian:
- Tiền xử lý HLD và BFS: \(O(n)\).
- Mỗi truy vấn (cập nhật hoặc tính toán) mất \(O(\log^2 n)\) do phải đi qua tối đa \(O(\log n)\) đoạn HLD và thao tác trên BIT mất \(O(\log n)\).
- Tổng thời gian: \(O(n + q \log^2 n)\), hoàn toàn chạy kịp thời gian cho giới hạn \(10^6\).
Bộ nhớ: \(O(n)\) để lưu trữ cây, các mảng HLD và cây BIT.

Code tham khảo

C++

#include <bits/stdc++.h>
using namespace std;

const int mx = 1e6 + 5;

int headedge[mx], to[mx * 2], nxt[mx * 2];
long long weight[mx * 2];
int cnt = 0;

void add(int u, int v, long long cst) {
    to[++cnt] = v;
    weight[cnt] = cst;
    nxt[cnt] = headedge[u];
    headedge[u] = cnt;
}

int s[mx], par[mx], dep[mx], sz[mx], heavy[mx];
long long dist[mx], w[mx], p[mx], bit1[mx], a[mx];
int hld[mx], pos[mx], revpos[mx];
__int128 bit2[mx];

int n, q;
long long totala = 0;
__int128 sum = 0;

void update1(int i, long long delta) {
    for (; i <= n; i += i & -i) bit1[i] += delta;
}

long long query1(int i) {
    long long s_val = 0;
    for (; i > 0; i -= i & -i) s_val += bit1[i];
    return s_val;
}

void update2(int i, __int128 delta) {
    for (; i <= n; i += i & -i) bit2[i] += delta;
}

__int128 query2(int i) {
    __int128 s_val = 0;
    for (; i > 0; i -= i & -i) s_val += bit2[i];
    return s_val;
}

void print128(__int128 num) {
    if (num == 0) {
        cout << "0\n";
        return;
    }
    if (num < 0) {
        cout << "-";
        num = -num;
    }
    char buf[40];
    int idx = 0;
    while (num > 0) {
        buf[idx++] = (char)('0' + (num % 10));
        num /= 10;
    }
    for (int i = idx - 1; i >= 0; i--) {
        cout << buf[i];
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q;
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        long long wt;
        cin >> u >> v >> wt;
        add(u, v, wt);
        add(v, u, wt);
    }

    queue<int> qu;
    qu.push(1);
    par[1] = 0;
    dep[1] = 0;
    dist[1] = 0;
    w[1] = 0;

    int idx = 0;
    while (!qu.empty()) {
        int u = qu.front();
        qu.pop();
        s[idx++] = u;

        for (int e = headedge[u]; e; e = nxt[e]) {
            int v = to[e];
            if (v != par[u]) {
                par[v] = u;
                dep[v] = dep[u] + 1;
                dist[v] = dist[u] + weight[e];
                w[v] = weight[e];
                qu.push(v);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        sz[i] = 1;
        heavy[i] = 0;
    }

    for (int i = n - 1; i >= 0; i--) {
        int u = s[i];
        if (par[u]) sz[par[u]] += sz[u];
    }

    for (int i = 0; i < n; i++) {
        int u = s[i];
        for (int e = headedge[u]; e; e = nxt[e]) {
            int v = to[e];
            if (v != par[u]) {
                if (heavy[u] == 0 || sz[v] > sz[heavy[u]]) {
                    heavy[u] = v;
                }
            }
        }
    }

    int timer = 0;
    for (int i = 0; i < n; i++) {
        int u = s[i];
        if (hld[u] == 0) {
            for (int v = u; v != 0; v = heavy[v]) {
                hld[v] = u;
                pos[v] = ++timer;
                revpos[timer] = v;
            }
        }
    }

    p[0] = 0;
    for (int i = 1; i <= n; i++) {
        p[i] = p[i - 1] + w[revpos[i]];
    }

    for (int step = 0; step < q + 1; step++) {
        int type;
        if (!(cin >> type)) break;
        if (type == 1) {
            int x;
            long long y;
            cin >> x >> y;
            long long res = y - a[x];
            if (res == 0) continue;

            a[x] = y;
            totala += res;
            sum += (__int128)res * dist[x];

            int curr = x;
            while (curr > 0) {
                int top = hld[curr];
                int l = pos[top];
                int r = pos[curr];

                update1(l, res);
                update1(r + 1, -res);
                update2(l, -(__int128)res * p[l - 1]);
                update2(r + 1, (__int128)res * p[r]);

                curr = par[top];
            }
        } else {
            int x;
            cin >> x;

            __int128 slca = 0;
            int curr = x;

            while (curr > 0) {
                int top = hld[curr];
                int l = pos[top];
                int r = pos[curr];

                __int128 sumr = (__int128)query1(r) * p[r] + query2(r);
                __int128 suml = (__int128)query1(l - 1) * p[l - 1] + query2(l - 1);

                slca += (sumr - suml);
                curr = par[top];
            }

            __int128 ans = (__int128)dist[x] * totala + sum - 2 * slca;
            print128(ans);
        }
    }
    return 0;
}

Python

Do giới hạn thời gian nghiêm ngặt (\(10^6\) thao tác và yêu cầu hiệu năng cao bằng C++), cài đặt bằng Python với cấu trúc dữ liệu phức tạp như HLD kết hợp BIT có thể không vượt qua được giới hạn thời gian (Time Limit Exceeded). Bài toán này khuyến khích sử dụng C++ với tối ưu hóa nhập xuất.

Bình luận

Tải bình luận...

Không có bình luận nào.