Ao tôm (Đề tự luyện HSG Tin quốc gia – Bài 4)

Nguồn: Đề tự luyện HSG Tin học quốc gia #04 – Bài 4 (đề tự soạn)Độ khó: KhóQHĐ trên câyHàm lồi tuyến tính từng khúcSlope trickHàng đợi ưu tiênGộp nhỏ vào lớn

Đề bài

Ao tôm. Có $N$ ao nối thành cây: ao 1 lấy nước từ sông, ao $i \ge 2$ nhận nước từ ao $p_i < i$. Đáy ao $i$ có cao độ $h_i$. Cần chọn cao độ mới $g_i$ (số nguyên) sao cho $g_i \le g_{p_i}$ với mọi $i \ge 2$. Nâng đáy ao $i$ thêm 1 đơn vị tốn $a_i$, hạ 1 đơn vị tốn $b_i$. Tìm tổng chi phí nhỏ nhất.

Dữ liệu vào: dòng 1: $N$ $(1 \le N \le 10^5)$; dòng 2: $p_2..p_N$; dòng 3: $h_1..h_N$ $(0 \le h_i \le 10^9)$; dòng 4: $a_1..a_N$; dòng 5: $b_1..b_N$ $(1 \le a_i, b_i \le 10^4)$.

Kết quả: chi phí nhỏ nhất.

Subtask 1 (10%): $N \le 100$, $h_i \le 100$.
Subtask 2 (15%): $N \le 2000$.
Subtask 3 (20%): $p_i = i - 1$ (các ao nối thành một dãy).
Subtask 4 (25%): mỗi ao cách ao 1 không quá 20 cống.
Subtask 5 (30%): không có ràng buộc gì thêm.

Giới hạn thời gian: C++ 1 giây, Python/PyPy 3 giây.

Input

6
1 1 1 2 4
8 5 1 3 2 6
3 2 4 3 1 3
2 4 1 4 3 3

Output

Giải thích

Chỉ có cặp $4 \to 6$ vi phạm ($6 > 3$). Nâng ao 4 lên 5 (tốn $2 \cdot 3 = 6$), hạ ao 6 xuống 5 (tốn $1 \cdot 3 = 3$): tổng 9. Chỉ hạ ao 6 xuống 3 cũng tốn 9. Không có cách nào rẻ hơn.

Dành cho học viênNộp bài trên ClueOJ

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.

Nộp bài Ao tôm

Lời mở đầu

Đây là bài cuối, bài "phân loại" của đề. Đề nghe rất hiền: chỉnh cao độ cho đúng chiều nước chảy với chi phí nhỏ nhất. Nhưng các cách tham lam tự nhiên ("ao nào cao hơn ao cha thì hạ xuống", "kéo ao cha lên bằng ao con cao nhất") đều sai, còn QHĐ thẳng thì phụ thuộc vào cao độ tới $10^9$. Lời giải đầy đủ dùng một kỹ thuật rất đẹp: biểu diễn cả một hàm số bằng một hàng đợi ưu tiên (người ta hay gọi là slope trick), rồi gộp nhỏ vào lớn trên cây.

Nhận xét 1: QHĐ trên cây theo "mức nước của ao cha"

Gọi $c_v(x)$ là chi phí sửa riêng ao $v$ về cao độ $x$: $c_v(x) = a_v (x - h_v)$ nếu $x \ge h_v$, $= b_v (h_v - x)$ nếu $x < h_v$ — hình chữ V lệch. Với mỗi ao $v$ định nghĩa:

$F_v(x)$ = chi phí nhỏ nhất để sửa cả nhánh gốc $v$ (ao $v$ và mọi ao nhận nước từ nó, trực tiếp hay gián tiếp) khi $g_v = x$;
$G_v(x)$ = chi phí nhỏ nhất cho nhánh gốc $v$ khi ao cha của $v$ có cao độ $x$, tức là $g_v$ được chọn tùy ý miễn $g_v \le x$.

$$F_v(x) = c_v(x) + \sum_{c \text{ là con của } v} G_c(x), \qquad G_v(x) = \min_{y \le x} F_v(y), \qquad \text{đáp án} = \min_x F_1(x).$$

Vì $p_i < i$ nên chỉ cần duyệt $v$ từ $N$ về $1$ là mọi ao con đã được tính trước ao cha — không cần DFS.

Hình 1. Trái: chi phí sửa một ao. Phải: lấy "min tiền tố" của một hàm lồi = giữ nguyên phần đi xuống, thay phần đi lên bằng một đường nằm ngang.

Cách 1QHĐ theo cao độ · 10%Cách 2Chỉ xét các h có sẵn · 25%Cách 3Dãy: slope trick · 45%Cách 4Cây nông: gộp ngây thơ · 50%Cách 5Gộp nhỏ vào lớn · 100%

Cách 1QHĐ theo từng cao độ – O(N·H) · 10%

Khi $h_i \le 100$: cao độ tối ưu chẳng bao giờ cần ra ngoài đoạn $[0, \max h]$ (đẩy một ao vượt ra ngoài chỉ làm tốn thêm mà không giúp ao nào). Vậy tính thẳng $F_v(x)$ và $G_v(x)$ với $x = 0..H$ ($H = \max h$) bằng công thức ở trên: $G_v$ là mảng min tiền tố của $F_v$, cộng dồn vào mảng acc của ao cha.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n;
    scanf("%d", &n);
    vector<int> par(n + 1, 0), h(n + 1), a(n + 1), b(n + 1);
    for (int i = 2; i <= n; i++) scanf("%d", &par[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
    int H = *max_element(h.begin() + 1, h.end());
    // acc[v][x] = tong cac G_c(x) cua cac ao con c cua v
    vector<vector<ll>> acc(n + 1, vector<ll>(H + 1, 0));
    ll ans = 0;
    for (int v = n; v >= 1; v--) {
        vector<ll> f(H + 1);
        for (int x = 0; x <= H; x++)            // f_v(x) = chi phi ao v + tong G_c(x)
            f[x] = acc[v][x] + (x > h[v] ? (ll)a[v] * (x - h[v]) : (ll)b[v] * (h[v] - x));
        for (int x = 1; x <= H; x++) f[x] = min(f[x], f[x - 1]);   // G_v(x) = min f_v(y), y <= x
        if (v == 1) ans = f[H];
        else for (int x = 0; x <= H; x++) acc[par[v]][x] += f[x];
    }
    printf("%lld\n", ans);
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    par = [0, 0] + [int(x) for x in data[1:n]]
    h = [0] + [int(x) for x in data[n:2 * n]]
    a = [0] + [int(x) for x in data[2 * n:3 * n]]
    b = [0] + [int(x) for x in data[3 * n:4 * n]]
    H = max(h[1:])
    acc = [[0] * (H + 1) for _ in range(n + 1)]   # acc[v][x] = tong G_c(x) cua cac ao con
    ans = 0
    for v in range(n, 0, -1):
        hv = h[v]; av = a[v]; bv = b[v]; s = acc[v]
        f = [s[x] + (av * (x - hv) if x > hv else bv * (hv - x)) for x in range(H + 1)]
        for x in range(1, H + 1):                 # G_v(x) = min f_v(y), y <= x
            if f[x - 1] < f[x]: f[x] = f[x - 1]
        if v == 1:
            ans = f[H]
        else:
            t = acc[par[v]]
            for x in range(H + 1):
                t[x] += f[x]
    print(ans)

main()

Không gian$O(N \cdot H)$

Thời gian$O(N \cdot H)$

Cách 2Chỉ cần xét các cao độ có sẵn – O(N²) · 25%

Khi $h$ tới $10^9$ ta cần nhận xét mạnh hơn.

Bổ đề

Luôn có một phương án tối ưu mà mọi $g_i$ đều thuộc tập $\{h_1, h_2, \ldots, h_N\}$.

Vì sao? Mỗi $c_v$ là hàm lồi, tuyến tính từng khúc, chỉ "gãy" tại $h_v$. Cộng các hàm như vậy vẫn được hàm lồi tuyến tính từng khúc, chỗ gãy là hợp các chỗ gãy; lấy min tiền tố của hàm lồi cũng chỉ cắt phần đi lên tại một chỗ gãy có sẵn. Quy nạp từ lá lên: mọi $F_v, G_v$ đều lồi và chỉ gãy tại các giá trị $h$. Một hàm tuyến tính từng khúc đạt min tại một điểm gãy, nên $F_1$ đạt min tại một $h$ nào đó; và với mức của ao cha là $x$, cao độ tốt nhất cho ao $v$ là $\min(x, x_v^*)$ với $x_v^*$ là điểm đáy của $F_v$ — cũng là một giá trị $h$. Đi từ ao 1 xuống, mọi $g_i$ đều thuộc tập $h$.

Vậy nén các $h$ khác nhau thành $D \le N$ giá trị rồi làm như Cách 1 trên $D$ giá trị đó: $O(N \cdot D) = O(N^2)$, đủ cho $N \le 2000$.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n;
    scanf("%d", &n);
    vector<int> par(n + 1, 0), h(n + 1), a(n + 1), b(n + 1);
    for (int i = 2; i <= n; i++) scanf("%d", &par[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
    vector<int> val(h.begin() + 1, h.end());     // chi can xet cac do cao co san
    sort(val.begin(), val.end()); val.erase(unique(val.begin(), val.end()), val.end());
    int D = val.size();
    vector<vector<ll>> acc(n + 1);
    ll ans = 0;
    for (int v = n; v >= 1; v--) {
        if (acc[v].empty()) acc[v].assign(D, 0);
        vector<ll>& f = acc[v];
        for (int j = 0; j < D; j++) {
            int x = val[j];
            f[j] += x > h[v] ? (ll)a[v] * (x - h[v]) : (ll)b[v] * (h[v] - x);
        }
        for (int j = 1; j < D; j++) f[j] = min(f[j], f[j - 1]);   // G_v
        if (v == 1) { ans = f[D - 1]; break; }
        vector<ll>& g = acc[par[v]];
        if (g.empty()) g.assign(D, 0);
        for (int j = 0; j < D; j++) g[j] += f[j];
        vector<ll>().swap(acc[v]);               // giai phong bo nho
    }
    printf("%lld\n", ans);
}

import sys
from itertools import accumulate
from operator import add

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    par = [0, 0] + [int(x) for x in data[1:n]]
    h = [0] + [int(x) for x in data[n:2 * n]]
    a = [0] + [int(x) for x in data[2 * n:3 * n]]
    b = [0] + [int(x) for x in data[3 * n:4 * n]]
    val = sorted(set(h[1:]))                       # chi can xet cac do cao co san
    D = len(val)
    acc = [None] * (n + 1)
    ans = 0
    for v in range(n, 0, -1):
        hv = h[v]; av = a[v]; bv = b[v]
        c = [av * (x - hv) if x > hv else bv * (hv - x) for x in val]
        f = c if acc[v] is None else list(map(add, acc[v], c))
        f = list(accumulate(f, min))               # G_v
        acc[v] = None
        if v == 1:
            ans = f[-1]
        else:
            p = par[v]
            acc[p] = f if acc[p] is None else list(map(add, acc[p], f))
    print(ans)

main()

Không gian$O(N \cdot D)$ (C++ giải phóng dần)

Thời gian$O(N \cdot D)$

Tham lam không được đâu!

Hai kiểu tham lam hay gặp: (1) đi từ ao 1 xuống, ao nào cao hơn ao cha thì hạ xuống bằng ao cha; (2) ngược lại, kéo ao cha lên. Cả hai đều sai vì có lúc nâng ao cha rẻ hơn hạ nhiều ao con (khi $a$ nhỏ, $b$ lớn), có lúc ngược lại — và quyết định ở một ao ảnh hưởng dây chuyền xuống cả nhánh. Ví dụ đề cố tình có hai cách cùng tốn 9 nên tham lam (1) vẫn "ăn may" in đúng 9!

Cách 3Các ao nối thành dãy: biểu diễn hàm bằng hàng đợi ưu tiên – O(N log N) · 45%

Để đi tiếp, ta cần lưu cả hàm $G_v$ mà không lưu từng giá trị. Mấu chốt: $G_v$ là hàm lồi, không tăng, gãy tại các $h$. Một hàm như vậy luôn viết được dưới dạng $$G_v(x) = M_v + \sum_{p \in S_v} \max(0,\ p - x),$$ trong đó $M_v$ là giá trị nhỏ nhất (đáy phẳng bên phải) và $S_v$ là một đa tập các điểm gãy: mỗi phần tử $p$ làm độ dốc bên trái nó giảm thêm 1. Ta lưu $S_v$ dưới dạng các cặp (cao độ, số đơn vị) trong một max-heap.

Bước 1 – cộng chi phí ao $v$. Viết $c_v(x) = (a_v + b_v)\max(0, h_v - x) + a_v (x - h_v)$ (kiểm tra: khi $x \ge h_v$ ra $a_v(x - h_v)$; khi $x < h_v$ ra $b_v(h_v - x)$). Nên $F_v = M + \sum_{p \in S} \max(0, p - x) + a_v(x - h_v)$ với $S$ là hợp các đa tập của các con cộng thêm $a_v + b_v$ đơn vị tại $h_v$, và $M$ là tổng các $M_c$.

Bước 2 – lấy min tiền tố. Bên phải mọi điểm gãy, $F_v$ có độ dốc $+a_v$; mỗi lần đi qua một đơn vị điểm gãy về bên trái thì độ dốc giảm 1. Vậy đáy của $F_v$ nằm ở đơn vị lớn thứ $a_v$. Lấy min tiền tố = cắt bỏ phần đi lên = bỏ $a_v$ đơn vị lớn nhất ra khỏi $S$. Gọi tổng cao độ của $a_v$ đơn vị bị bỏ là $popped$, một phép biến đổi nhỏ cho $$M_v = \sum_c M_c + popped - a_v \cdot h_v.$$

Thuật toán cho mỗi ao v (duyệt v từ N về 1)

1) Đẩy cặp $(h_v,\ a_v + b_v)$ vào heap. 2) Rút ra đúng $a_v$ đơn vị lớn nhất (cặp nào rút một phần thì đẩy phần còn lại vào lại), cộng dồn vào $popped$. 3) $ans \mathrel{+}= popped - a_v h_v$. Cuối cùng $ans = M_1$ chính là đáp án.

Kiểm tra với một ao lá: đẩy $(h, a+b)$, rút $a$ đơn vị tại $h$ nên $popped = a \cdot h$ và $M = 0$ — đúng, một ao đứng một mình không phải sửa gì.

Với dãy ($p_i = i - 1$), mỗi ao chỉ có đúng một con, nên chỉ cần một heap duy nhất dùng chung từ ao $N$ về ao 1. Mô phỏng dưới đây vẽ hàm $G$ hiện tại từ đa tập điểm gãy (đường xanh) và heap:

Cao độ h (ao 1 → N) Giá nâng a Giá hạ b

Ví dụ nhanh:

Code Cách 3 (nếu không phải dãy thì quay về Cách 2, nên ăn được subtask 1, 2, 3). Bản Python mã hóa mỗi cặp thành một số nguyên $((10^9 - h) \ll 15) \mid \text{số đơn vị}$ để dùng heapq (min-heap) cho nhanh: số nhỏ nhất ứng với cao độ lớn nhất, và giảm số đơn vị của đỉnh heap chỉ cần trừ trực tiếp vào H[0] mà không phá thứ tự heap.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<int> par, h, a, b;
ll cach2() {                                     // nhu Cach 2
    vector<int> val(h.begin() + 1, h.end());
    sort(val.begin(), val.end()); val.erase(unique(val.begin(), val.end()), val.end());
    int D = val.size();
    vector<vector<ll>> acc(n + 1);
    for (int v = n; v >= 1; v--) {
        if (acc[v].empty()) acc[v].assign(D, 0);
        vector<ll>& f = acc[v];
        for (int j = 0; j < D; j++) { int x = val[j]; f[j] += x > h[v] ? (ll)a[v] * (x - h[v]) : (ll)b[v] * (h[v] - x); }
        for (int j = 1; j < D; j++) f[j] = min(f[j], f[j - 1]);
        if (v == 1) return f[D - 1];
        vector<ll>& g = acc[par[v]];
        if (g.empty()) g.assign(D, 0);
        for (int j = 0; j < D; j++) g[j] += f[j];
        vector<ll>().swap(acc[v]);
    }
    return 0;
}
int main() {
    scanf("%d", &n);
    par.assign(n + 1, 0); h.resize(n + 1); a.resize(n + 1); b.resize(n + 1);
    bool chain = true;
    for (int i = 2; i <= n; i++) { scanf("%d", &par[i]); if (par[i] != i - 1) chain = false; }
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
    if (!chain) { printf("%lld\n", cach2()); return 0; }
    priority_queue<pair<int, int>> pq;           // cac diem gay (do cao, so don vi) cua G
    ll ans = 0;
    for (int v = n; v >= 1; v--) {               // di tu ao cuoi chuoi ve ao 1
        pq.push({h[v], a[v] + b[v]});
        int need = a[v]; ll popped = 0;
        while (need > 0) {
            auto [x, c] = pq.top(); pq.pop();
            int d = min(c, need);
            popped += (ll)x * d; need -= d;
            if (c > d) pq.push({x, c - d});
        }
        ans += popped - (ll)a[v] * h[v];
    }
    printf("%lld\n", ans);
}

import sys
from heapq import heappush, heappop
from itertools import accumulate
from operator import add

def cach2(n, par, h, a, b):                        # nhu Cach 2
    val = sorted(set(h[1:]))
    acc = [None] * (n + 1)
    for v in range(n, 0, -1):
        hv = h[v]; av = a[v]; bv = b[v]
        c = [av * (x - hv) if x > hv else bv * (hv - x) for x in val]
        f = c if acc[v] is None else list(map(add, acc[v], c))
        f = list(accumulate(f, min)); acc[v] = None
        if v == 1: return f[-1]
        p = par[v]
        acc[p] = f if acc[p] is None else list(map(add, acc[p], f))

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    par = [0, 0] + [int(x) for x in data[1:n]]
    h = [0] + [int(x) for x in data[n:2 * n]]
    a = [0] + [int(x) for x in data[2 * n:3 * n]]
    b = [0] + [int(x) for x in data[3 * n:4 * n]]
    if any(par[i] != i - 1 for i in range(2, n + 1)):
        print(cach2(n, par, h, a, b)); return
    MAXH = 10**9; SH = 15; MASK = (1 << SH) - 1
    H = []; ans = 0                                # mot heap duy nhat cho ca chuoi
    for v in range(n, 0, -1):
        hv = h[v]; av = a[v]
        heappush(H, ((MAXH - hv) << SH) | (av + b[v]))
        need = av; popped = 0
        while need:
            top = H[0]; c = top & MASK; x = MAXH - (top >> SH)
            if c <= need:
                heappop(H); popped += x * c; need -= c
            else:
                H[0] = top - need; popped += x * need; need = 0
        ans += popped - av * hv
    print(ans)

main()

Không gian$O(N)$

Thời gian$O(N \log N)$ (khi là dãy)

Vì sao số cặp trong heap không bùng nổ?

Mỗi ao đẩy vào đúng một cặp. Khi rút $a_v$ đơn vị, mọi cặp bị rút hết thì biến mất, chỉ có nhiều nhất một cặp bị rút một phần và được đẩy lại. Nên tổng số thao tác heap là $O(N)$, mỗi thao tác $O(\log N)$.

Cách 4Cây nông: gộp ngây thơ – O(N·D·log N) · 50%

Với cây bất kỳ, $F_v = c_v + \sum_c G_c$: cộng các hàm dạng $M + \sum \max(0, p - x)$ chỉ là gộp các đa tập và cộng các $M$. Vậy cách tự nhiên nhất: khi xử lý xong ao $v$, đổ toàn bộ heap của $v$ sang heap của ao cha $p_v$. Vì $p_v < v$, khi tới lượt ao cha thì heap của nó đã chứa đủ các đa tập của mọi con.

Mỗi cặp bị đổ một lần cho mỗi "bậc" nó đi lên. Nếu mọi ao cách ao 1 không quá $D = 20$ cống thì tổng số lần đẩy không quá $N \cdot D$ — rất nhanh. Nhưng với dãy dài $10^5$ ao, heap gần như lớn dần lên đều đặn và bị đổ đi đổ lại: $O(N^2 \log N)$, chạy không kịp.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n;
    scanf("%d", &n);
    vector<int> par(n + 1, 0), h(n + 1), a(n + 1), b(n + 1);
    for (int i = 2; i <= n; i++) scanf("%d", &par[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
    vector<priority_queue<pair<int, int>>> pq(n + 1);
    ll ans = 0;
    for (int v = n; v >= 1; v--) {
        pq[v].push({h[v], a[v] + b[v]});
        int need = a[v]; ll popped = 0;
        while (need > 0) {
            auto [x, c] = pq[v].top(); pq[v].pop();
            int d = min(c, need);
            popped += (ll)x * d; need -= d;
            if (c > d) pq[v].push({x, c - d});
        }
        ans += popped - (ll)a[v] * h[v];
        if (v > 1)                               // gop ngay tho: day het sang heap cua ao cha
            while (!pq[v].empty()) { pq[par[v]].push(pq[v].top()); pq[v].pop(); }
    }
    printf("%lld\n", ans);
}

import sys
from heapq import heappush, heappop

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    par = [0, 0] + [int(x) for x in data[1:n]]
    h = [0] + [int(x) for x in data[n:2 * n]]
    a = [0] + [int(x) for x in data[2 * n:3 * n]]
    b = [0] + [int(x) for x in data[3 * n:4 * n]]
    MAXH = 10**9; SH = 15; MASK = (1 << SH) - 1
    pq = [None] + [[] for _ in range(n)]
    ans = 0
    for v in range(n, 0, -1):
        H = pq[v]; hv = h[v]; av = a[v]
        heappush(H, ((MAXH - hv) << SH) | (av + b[v]))
        need = av; popped = 0
        while need:
            top = H[0]; c = top & MASK; x = MAXH - (top >> SH)
            if c <= need:
                heappop(H); popped += x * c; need -= c
            else:
                H[0] = top - need; popped += x * need; need = 0
        ans += popped - av * hv
        if v > 1:                                  # gop ngay tho: day het sang heap cua ao cha
            G = pq[par[v]]
            for e in H:
                heappush(G, e)
            pq[v] = None
    print(ans)

main()

Không gian$O(N)$

Thời gian$O(N \cdot D \cdot \log N)$ với $D$ là độ sâu của cây

Cách 5Gộp nhỏ vào lớn – O(N log² N) · 100%

Sửa đúng một chỗ của Cách 4: khi gộp heap của ao $v$ vào heap của ao cha $p$, nếu heap của $p$ đang nhỏ hơn thì đổi chỗ hai heap trước (đổi chỗ hai priority_queue là $O(1)$), rồi mới đổ heap nhỏ vào heap lớn.

Vì sao chỉ O(N log² N)?

Mỗi lần một cặp bị đổ sang heap khác, nó nằm ở heap nhỏ hơn, nên heap chứa nó sau khi gộp có kích thước ít nhất gấp đôi. Kích thước không vượt quá $N$, vậy mỗi cặp bị đổ tối đa $\log_2 N$ lần. Tổng $O(N \log N)$ lần đẩy, mỗi lần $O(\log N)$. (Các lần rút $a_v$ đơn vị vẫn chỉ tốn $O(N \log N)$ như Cách 3.)

Mô phỏng trên cây nhỏ: mỗi bước là một ao, bảng bên dưới là heap của các ao đang "sống".

p_2..p_N h a b

Ví dụ nhanh:

Code đầy đủ:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n;
    scanf("%d", &n);
    vector<int> par(n + 1, 0), h(n + 1), a(n + 1), b(n + 1);
    for (int i = 2; i <= n; i++) scanf("%d", &par[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
    // pq[v]: cac diem gay (do cao, so don vi) cua ham G_v, max-heap
    vector<priority_queue<pair<int, int>>> pq(n + 1);
    ll ans = 0;
    for (int v = n; v >= 1; v--) {               // p_v < v nen moi ao con duoc xu ly truoc ao cha
        pq[v].push({h[v], a[v] + b[v]});        // cong ham a*max(0,x-h) + b*max(0,h-x)
        int need = a[v];                         // bo a[v] don vi doc duong lon nhat
        ll popped = 0;
        while (need > 0) {
            auto [x, c] = pq[v].top(); pq[v].pop();
            int d = min(c, need);
            popped += (ll)x * d; need -= d;
            if (c > d) pq[v].push({x, c - d});
        }
        ans += popped - (ll)a[v] * h[v];
        if (v > 1) {                             // gop vao ao cha: nho vao lon
            int p = par[v];
            if (pq[p].size() < pq[v].size()) swap(pq[p], pq[v]);
            while (!pq[v].empty()) { pq[p].push(pq[v].top()); pq[v].pop(); }
        }
    }
    printf("%lld\n", ans);
}

import sys
from heapq import heappush, heappop

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    par = [0, 0] + [int(x) for x in data[1:n]]
    h = [0] + [int(x) for x in data[n:2 * n]]
    a = [0] + [int(x) for x in data[2 * n:3 * n]]
    b = [0] + [int(x) for x in data[3 * n:4 * n]]
    # moi phan tu heap la mot so nguyen: ((MAXH - do cao) << 15) | so don vi  -> heap min = do cao lon nhat
    MAXH = 10**9; SH = 15; MASK = (1 << SH) - 1
    pq = [None] * (n + 1)
    for v in range(1, n + 1):
        pq[v] = []
    ans = 0
    for v in range(n, 0, -1):                  # p_v < v nen moi ao con duoc xu ly truoc ao cha
        H = pq[v]; hv = h[v]; av = a[v]
        heappush(H, ((MAXH - hv) << SH) | (av + b[v]))
        need = av; popped = 0
        while need:                            # bo a[v] don vi doc duong lon nhat
            top = H[0]; c = top & MASK; x = MAXH - (top >> SH)
            if c <= need:
                heappop(H); popped += x * c; need -= c
            else:
                H[0] = top - need; popped += x * need; need = 0
        ans += popped - av * hv
        if v > 1:                              # gop vao ao cha: nho vao lon
            p = par[v]; G = pq[p]
            if len(G) < len(H):
                pq[p] = H; H, G = G, H
            for e in H:
                heappush(G, e)
            pq[v] = None
    sys.stdout.write(str(ans) + "\n")

main()

Không gian$O(N)$

Thời gian$O(N \log^2 N)$

Những chỗ dễ mất điểm

Tràn số: đáp án tới cỡ $10^5 \cdot 10^4 \cdot 10^9 = 10^{18}$, phải dùng long long cho $popped$ và $ans$ (vẫn vừa trong giới hạn $9{,}2 \cdot 10^{18}$).
Nhầm nâng/hạ: số đơn vị bị rút là $a_v$ (giá nâng) vì đó là độ dốc bên phải của $F_v$. Nhầm thành $b_v$ là sai ngay khi $a \ne b$.
Gộp mà không so kích thước: "heap cha rỗng thì đổi chỗ, không thì đổ con vào cha" trông giống gộp nhỏ vào lớn nhưng vẫn $O(N^2)$ khi ao cha đã nhận vài ao con nhỏ trước khi nhận một nhánh rất lớn.

Chạy tay từng dòng code C++ ở trên (để dễ theo dõi: $N \le 10$):

C++▶ Chạy tay từng dòng codeMỗi ao: đẩy điểm gãy, rút a đơn vị lớn nhất, rồi gộp heap nhỏ vào heap lớn của ao cha.

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3typedef long long ll;

4int main() {

5 int n;

6 scanf("%d", &n);

7 vector<int> par(n + 1, 0), h(n + 1), a(n + 1), b(n + 1);

8 for (int i = 2; i <= n; i++) scanf("%d", &par[i]);

9 for (int i = 1; i <= n; i++) scanf("%d", &h[i]);

10 for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

11 for (int i = 1; i <= n; i++) scanf("%d", &b[i]);

12 // pq[v]: cac diem gay (do cao, so don vi) cua ham G_v, max-heap

13 vector<priority_queue<pair<int, int>>> pq(n + 1);

14 ll ans = 0;

15 for (int v = n; v >= 1; v--) { // p_v < v nen moi ao con duoc xu ly truoc ao cha

16 pq[v].push({h[v], a[v] + b[v]}); // cong ham a*max(0,x-h) + b*max(0,h-x)

17 int need = a[v]; // bo a[v] don vi doc duong lon nhat

18 ll popped = 0;

19 while (need > 0) {

20 auto [x, c] = pq[v].top(); pq[v].pop();

21 int d = min(c, need);

22 popped += (ll)x * d; need -= d;

23 if (c > d) pq[v].push({x, c - d});

24 }

25 ans += popped - (ll)a[v] * h[v];

26 if (v > 1) { // gop vao ao cha: nho vao lon

27 int p = par[v];

28 if (pq[p].size() < pq[v].size()) swap(pq[p], pq[v]);

29 while (!pq[v].empty()) { pq[p].push(pq[v].top()); pq[v].pop(); }

30 }

31 }

32 printf("%lld\n", ans);

33}

Bộ test chấm "bắt" những lỗi nào?

Bộ test có 36 test (8 – 7 – 6 – 7 – 8 theo subtask). Các test lớn có $N = 10^5$, cao độ tới $10^9$, đáp án tới cỡ $10^{16}$; chi phí được sinh theo nhiều kiểu: ngẫu nhiên, "nâng rẻ – hạ đắt" (heap lớn dần, làm các cách gộp chậm lộ ra), trộn hai kiểu. Subtask 5 dùng cây có một "xương sống" dài 40000–80000 ao, các ao còn lại (chỉ số lớn) treo vào xương sống — để ao cha luôn có sẵn vài phần tử trước khi nhận heap khổng lồ của ao con.

Cách làm	Sub 1	Sub 2	Sub 3	Sub 4	Sub 5	Điểm
Cách 1 – QHĐ theo từng cao độ	8/8	TLE	TLE	TLE	TLE	10
Cách 2 – chỉ xét các h có sẵn, O(N²)	8/8	7/7	TLE	TLE	TLE	25
Cách 3 – dãy: slope trick một heap	8/8	7/7	6/6	TLE	TLE	45
Cách 4 – gộp ngây thơ	8/8	7/7	TLE	7/7	TLE	50
Cách 5 – gộp nhỏ vào lớn (lời giải đầy đủ)	8/8	7/7	6/6	7/7	8/8	100
Sai: gộp không so kích thước (heap cha rỗng mới đổi chỗ)	8/8	7/7	6/6	7/7	TLE	70
Sai: chi phí kiểu int	8/8	0/7	0/6	0/7	0/8	10
Sai: nhầm giá nâng với giá hạ	3/8	0/7	0/6	0/7	0/8	3,75
Sai: tham lam "ao cao hơn ao cha thì hạ xuống"	2/8	0/7	0/6	0/7	0/8	2,5

Để ý: ví dụ trong đề được chọn sao cho cả bốn lời giải sai ở trên đều in đúng 9 — tham lam "hạ ao con" tình cờ có cùng chi phí 9 với phương án tối ưu, nhầm $a$ với $b$ cũng ra 9, còn tràn số và gộp sai cách thì ví dụ nhỏ không thể lộ ra.

Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: lời giải chuẩn chạy tối đa 0,27 giây (giới hạn 1 giây); các ô TLE đều chạy quá 3 giây. Lời giải chuẩn được đối chiếu với chương trình vét cạn (thử mọi cách chọn cao độ) trên 800 test nhỏ và với QHĐ Cách 2 trên 300 test vừa, không lệch test nào; bản Python cho kết quả trùng khớp trên mọi test và chạy tối đa khoảng 1,5 giây ngay cả trên CPython.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇

Lập Trình Thuật Toán

Ao tôm (Đề tự luyện HSG Tin quốc gia – Bài 4)

Đề bài

Lời mở đầu

Nhận xét 1: QHĐ trên cây theo "mức nước của ao cha"

Cách 1QHĐ theo từng cao độ – O(N·H) · 10%

Cách 2Chỉ cần xét các cao độ có sẵn – O(N²) · 25%

Cách 3Các ao nối thành dãy: biểu diễn hàm bằng hàng đợi ưu tiên – O(N log N) · 45%

Cách 4Cây nông: gộp ngây thơ – O(N·D·log N) · 50%

Cách 5Gộp nhỏ vào lớn – O(N log² N) · 100%

Bộ test chấm "bắt" những lỗi nào?

Nhận xét

Đăng nhận xét

Dữ liệu trang web (tự động – không xoá)

Hướng dẫn tham gia Thi thử HSG Tin học hàng tuần trên ClueOJ (từ đăng ký tài khoản đến lúc vào phòng thi)

Khóa học luyện thi chuyên Tin, HSG Tin học – lập trình thuật toán C++