Cây là dạng đồ thị đặc biệt không có chu trình. Luyện tập các kỹ thuật quy hoạch động trên cây, nhảy nhị phân và trải phẳng cây để giải quyết truy vấn hiệu quả.
bài tập có chấm code
Bài tập theo chuyên đề, có đề bài, ví dụ và starter code riêng.
cơ bản
Củng cố nền tảng và làm quen với kỹ thuật cốt lõi.
trung bình
Kết hợp nhiều bước suy luận để vận dụng kiến thức.
nâng cao
Thử thách tối ưu, cấu trúc dữ liệu và thuật toán chuyên sâu.
Biểu diễn cây có gốc, duyệt DFS tính bậc, chiều cao và kích thước cây con.
Tìm khoảng cách lớn nhất giữa hai nút trên cây bằng 2 lần duyệt BFS/DFS.
Tính toán giá trị tối ưu của các cây con từ lá lên gốc (Tree DP).
Thuật toán Binary Lifting trả lời truy vấn LCA trong thời gian O(log N).
Xử lý cây như đồ thị có hướng trong khi cạnh của cây là vô hướng (cần truyền nút cha parent để tránh duyệt ngược).
Quên khởi tạo bảng nhảy up[N][20] cho thuật toán Binary Lifting.
Trong mỗi mức độ, bài tập được xếp từ dễ nhất đến khó nhất — hãy đi theo số bước.
Thuật toán chuyên sâu: quy hoạch động, đồ thị, cây.
Cho một cây có gốc tại đỉnh 1 gồm N đỉnh. Mỗi đỉnh u có một giá trị Vu. Bạn cần chọn đúng K đỉnh trên cây sao cho: Nếu một đỉnh u (u ≠ 1) được chọn thì đỉnh cha p(u) của nó cũng…
Cho một cây có gốc tại đỉnh 1 gồm N đỉnh (được đánh số từ 1 đến N). Mỗi đỉnh i có một giá trị Vi không âm.
Duy trì một rừng cây động (rừng gồm các cây vô hướng) với các thao tác liên kết (link), cắt (cut) và truy vấn tổng trọng số các đỉnh trên đường đi giữa 2 đỉnh bằng Link-Cut Tree (L…
Cho một cây vô hướng gồm N đỉnh (đánh số từ 1 đến N) và số nguyên dương K.
Cho một cây gồm N đỉnh (1 ≤ N ≤ 105) và số nguyên K (1 ≤ K ≤ N). Khoảng cách giữa hai đỉnh u và v là số lượng cạnh trên đường đi đơn giữa chúng.
Cho một mảng biểu diễn cây tìm kiếm nhị phân (BST) được xây dựng bằng cách chèn lần lượt N số nguyên phân biệt vào cây ban đầu rỗng. Hãy tìm giá trị của tổ tiên chung gần nhất (LCA…
Cấu trúc dữ liệu nâng cao và nhiều bước chứng minh.
Cho một cây vô hướng gồm N đỉnh (đánh số từ 1 đến N).
Cho một cây gồm N đỉnh (1 ≤ N ≤ 2 · 105) được đánh số từ 1 đến N. Hãy tìm:
Cho chuỗi tuần tự hóa của một cây nhị phân theo thứ tự BFS (các nút ngăn cách bởi dấu phẩy, nút rỗng ký hiệu là null). Hãy khôi phục lại cây nhị phân và in ra tổng giá trị của tất…
Cho một cây gồm N đỉnh (đánh số từ 1 đến N). Mỗi đỉnh u có một trọng số nguyên không âm Wu.
Cho một cây vô hướng gồm N đỉnh (đánh số từ 1 đến N) và N - 1 cạnh. Khoảng cách giữa hai đỉnh trên cây là số cạnh trên đường đi đơn nối giữa hai đỉnh đó.
Cho một cây có gốc tại đỉnh 1 gồm N đỉnh. Mỗi đỉnh ban đầu có giá trị Vu. Bạn cần xử lý Q truy vấn:
Ràng buộc chặt về thời gian và bộ nhớ — mức thi đấu.
Cho một cây có trọng số gồm N đỉnh (đánh số từ 1 đến N, gốc là đỉnh 1) và N - 1 cạnh có trọng số nguyên.
Hệ thống cây phân cấp bài giảng và chủ đề tại AI Empire Academy gồm N nút được đánh số từ 1 đến N, trong đó nút 1 là nút gốc (Root). Cây có N-1 cạnh nối giữa các nút.
Cho một cây gồm N đỉnh (1 ≤ N ≤ 2 · 105) được đánh số từ 1 đến N. Với mỗi đỉnh i (1 ≤ i ≤ N), hãy tính tổng khoảng cách từ đỉnh i tới tất cả các đỉnh còn lại trên cây:
Cho một cây gồm N đỉnh được đánh số từ 1 đến N với gốc là đỉnh 1. Ban đầu, mỗi đỉnh i có một giá trị số nguyên Vi. Cần xử lý Q truy vấn thuộc 2 loại:
Cho một cây có gốc gồm N đỉnh (đánh số từ 1 đến N, gốc là đỉnh 1). Mỗi đỉnh u được gán một màu nguyên dương Cu.
Cho một cây có gốc gồm N đỉnh (đánh số từ 1 đến N, gốc là đỉnh 1). Mỗi đỉnh u có hai giá trị trọng số Au và Bu.