Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Cây con nối tối thiểu

    Cho cây gồm nnn đỉnh với các cạnh có trọng số dương. Mỗi truy vấn cho một tập đỉnh được đánh dấu {v1,…,vk}\{v_1, \dots, v_k\}{v1​,…,vk​}. Hãy tính tổng trọng số nhỏ nhất các cạnh của một cây con liên thông chứa tất cả các đỉnh được đánh dấu (cây Steiner trên cây, chính là cây con tối thiểu nối các đỉnh đó).

    Gợi ý: sắp xếp các đỉnh đánh dấu theo thời điểm vào DFS, khi đó tổng khoảng cách giữa các cặp liên tiếp (vòng tròn) đúng bằng hai lần tổng trọng số cây con cần tìm. Sử dụng LCA bằng nhảy nhị phân.

    • Định dạng đầu vào:

      Dòng đầu chứa nnn và qqq. n−1n-1n−1 dòng tiếp theo, mỗi dòng ba số u v wu\ v\ wu v w. Mỗi truy vấn gồm một dòng: số kkk rồi kkk chỉ số đỉnh được đánh dấu.

    • Ràng buộc đầu vào:

      1≤n,q≤2⋅1051 \le n, q \le 2\cdot10^51≤n,q≤2⋅105, 1≤w≤1061 \le w \le 10^61≤w≤106, tổng kkk trên tất cả truy vấn không quá 2⋅1052\cdot10^52⋅105. Gốc là đỉnh 111.

    • Định dạng đầu ra:

      Với mỗi truy vấn, in tổng trọng số cây con tối thiểu trên một dòng.

    Ví dụ:

    Đầu vào:

    5 2
1 2 2
1 3 3
3 4 1
3 5 4
3 2 4 5
1 2

    Đầu ra:

    10
0

    Giải thích:

    Tập {2,4,5}: cây con nối chúng gồm các cạnh 1-2 (2), 1-3 (3), 3-4 (1), 3-5 (4), tổng 10. Truy vấn thứ hai chỉ có đỉnh 2 nên cây con rỗng, tổng 0.

    Đang tải editor...