Quốc gia JOI gồm \(N\) hòn đảo, được đánh số từ \(1\) đến \(N\). Ban đầu không có cây cầu nào nối các đảo, khiến cuộc sống của người dân gặp nhiều bất tiện. Bạn là bộ trưởng của quốc gia JOI và quyết định thực hiện một dự án công để xây cầu. Có \(M\) kế hoạch xây cầu hai chiều. Kế hoạch \(j\) nối \(A_j\) với \(B_j\) với chi phí \(C_j\); mọi chi phí đôi một khác nhau, và nếu thực hiện tất cả kế hoạch thì đồ thị liên thông.

Vì ngân sách quốc gia có hạn, bạn quyết định thực hiện dự án như sau: chọn một đảo \(s\) làm thủ đô, rồi thực hiện đúng \(N-1\) lần: trong các kế hoạch chưa thực hiện có đúng một đầu cầu đã đi được từ thủ đô và đầu kia chưa đi được, chọn kế hoạch rẻ nhất và xây cầu đó. Các điều kiện trên bảo đảm mỗi bước luôn có lựa chọn duy nhất và cuối cùng mọi đảo liên thông.

Rin đang cân nhắc chuyển đến sống tại quốc gia JOI. Để lựa chọn nơi ở, cô tính độ bất tiện của mỗi hòn đảo như sau. Gọi \(D_{s,i}\) là số cầu đã xây cho đến thời điểm đảo \(i\) lần đầu đi được từ thủ đô \(s\); đặt \(D_{i,i}=0\). Độ bất tiện của đảo \(i\) là \(\sum_{s=1}^{N}D_{s,i}\). Hãy trả lời độ bất tiện của \(Q\) đảo \(X_1,\ldots,X_Q\) mà Rin đang cân nhắc chuyển đến.

Dữ liệu vào

Dòng đầu chứa \(N,M,Q\). \(M\) dòng tiếp theo, dòng \(j\) chứa \(A_j,B_j,C_j\). \(Q\) dòng cuối lần lượt chứa \(X_1,X_2,\ldots,X_Q\), mỗi giá trị trên một dòng.

Dữ liệu ra

In \(Q\) dòng; dòng \(k\) là độ bất tiện của đảo \(X_k\).

Ràng buộc

• \(2\le N\le300\,000\), \(1\le M\le600\,000\), \(1\le Q\le N\).
• \(1\le A_j<B_j\le N\) và \(1\le C_j\le10^9\).
• Đồ thị tạo bởi toàn bộ \(M\) kế hoạch liên thông; \(C_1,C_2,\ldots,C_M\) đôi một khác nhau.
• \(1\le X_k\le N\) và \(X_1,X_2,\ldots,X_Q\) đôi một khác nhau.
• Mọi giá trị số trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(5\) điểm: \(N,M\le2000\).
2. \(8\) điểm: \(N\le2000\).
3. \(9\) điểm: \(M=N-1\), \(A_j=j\), \(B_j=j+1\) với mọi \(1\le j\le M\), và \(Q=1\).
4. \(18\) điểm: \(M=N-1\), \(A_j=j\), \(B_j=j+1\) với mọi \(1\le j\le M\).
5. \(28\) điểm: \(Q=1\).
6. \(32\) điểm: không có ràng buộc thêm.

Ví dụ

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

7
3

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

12
8
7
10
13

10 20 1
1 2 808642746
1 3 990324141
1 4 69919024
1 5 794837863
3 6 84751636
1 7 491226767
3 8 314795065
1 9 347506932
1 10 709806198
2 3 103026123
9 10 270175384
4 8 133038160
4 10 592110162
2 10 708615085
6 10 262209760
5 10 75049025
7 9 367273075
6 9 264231132
3 10 909786421
2 7 135810916
10

43

Nguồn

JOI 2025/2026 Semifinal Stage, bài New Bridge. Tài liệu gốc của Japanese Committee for IOI được phát hành theo CC BY-SA 4.0.