USACO 2018 - Tháng 1 - Hạng Vàng

Trong thời gian rảnh, bác nông dân John đã tạo một dịch vụ chia sẻ video mới mang tên MooTube. Trên MooTube, đàn bò của ông có thể quay, chia sẻ và khám phá nhiều video thú vị. Đàn bò đã đăng \(N\) video (\(1 \leq N \leq 100{,}000\)), được đánh số thuận tiện từ \(1 \ldots N\). Tuy nhiên, bác nông dân John vẫn chưa tìm ra cách giúp đàn bò khám phá những video mới mà chúng có thể yêu thích.

Bác nông dân John muốn tạo một danh sách “video được đề xuất” cho mỗi video trên MooTube. Nhờ đó, đàn bò sẽ được giới thiệu những video liên quan nhất đến các video chúng đã xem.

Bác nông dân John nghĩ ra một thước đo gọi là “độ liên quan”, đúng như tên gọi, dùng để xác định mức độ liên quan giữa hai video. Ông chọn \(N-1\) cặp video và tự tính độ liên quan của từng cặp. Sau đó, ông hình dung các video như một mạng lưới, trong đó mỗi video là một nút và \(N-1\) cặp video mà ông đã xem xét được nối với nhau. Thật thuận tiện, bác nông dân John đã chọn \(N-1\) cặp sao cho từ bất kỳ video nào cũng có đúng một cách để đi theo một đường gồm các liên kết đến bất kỳ video nào khác. Ông quyết định định nghĩa độ liên quan của một cặp video là độ liên quan nhỏ nhất của một liên kết trên đường đi này.

Bác nông dân John muốn chọn một giá trị \(K\) sao cho bên cạnh một video MooTube bất kỳ, tất cả các video khác có độ liên quan với video đó ít nhất là \(K\) đều được đề xuất. Tuy nhiên, ông lo rằng quá nhiều video sẽ được đề xuất cho đàn bò, khiến chúng xao nhãng việc sản xuất sữa! Vì vậy, ông muốn cẩn thận chọn một giá trị \(K\) phù hợp. Bác nông dân John cần bạn giúp trả lời một số câu hỏi về các video được đề xuất ứng với những giá trị \(K\) nhất định.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(Q\) (\(1 \leq Q \leq 100{,}000\)).

Mỗi dòng trong \(N-1\) dòng tiếp theo mô tả một cặp video mà bác nông dân John tự so sánh. Mỗi dòng chứa ba số nguyên \(p_i\), \(q_i\) và \(r_i\) (\(1 \leq p_i, q_i \leq N\), \(1 \leq r_i \leq 1{,}000{,}000{,}000\)), cho biết video \(p_i\) và video \(q_i\) được nối với nhau bằng một liên kết có độ liên quan \(r_i\).

\(Q\) dòng tiếp theo mô tả \(Q\) câu hỏi của bác nông dân John. Mỗi dòng chứa hai số nguyên \(k_i\) và \(v_i\) (\(1 \leq k_i \leq 1{,}000{,}000{,}000\), \(1 \leq v_i \leq N\)), cho biết câu hỏi thứ \(i\) của ông là có bao nhiêu video sẽ được đề xuất cho người xem video \(v_i\) nếu \(K=k_i\).

Dữ liệu ra

In ra \(Q\) dòng. Trên dòng thứ \(i\), in ra câu trả lời cho câu hỏi thứ \(i\) của bác nông dân John.

Ví dụ

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

3
0
2

Nguồn

USACO 2018 January Contest, Gold — MooTube

Tác giả bài toán: Jay Leeds.

Cuối cùng cũng bị dồn vào đường cùng, Bessie đã lẩn trốn trong một trang trại hẻo lánh. Trang trại gồm \(N\) chuồng bò (\(2 \leq N \leq 10^5\)) và \(N-1\) đường hầm hai chiều nối các chuồng, sao cho giữa mọi cặp chuồng đều có một đường đi duy nhất. Mỗi chuồng có đúng một đường hầm nối với nó đều là một lối thoát. Khi trời sáng, Bessie sẽ xuất hiện tại một chuồng nào đó và cố gắng đi đến một lối thoát.

Nhưng ngay khi Bessie xuất hiện, lực lượng hành pháp sẽ có thể xác định chính xác vị trí của cô. Khi đó, một số nông dân sẽ bắt đầu từ các chuồng là lối thoát và cố gắng bắt Bessie. Những người nông dân di chuyển với cùng tốc độ như Bessie (vì vậy trong mỗi bước thời gian, mỗi nông dân có thể đi từ một chuồng sang một chuồng kề nó). Những người nông dân luôn biết Bessie ở đâu, và Bessie cũng luôn biết họ ở đâu. Những người nông dân bắt được Bessie nếu tại bất kỳ thời điểm nào có một nông dân ở cùng chuồng với Bessie hoặc đang đi qua cùng một đường hầm với Bessie. Ngược lại, Bessie trốn thoát nếu cô đến được một chuồng là lối thoát trước khi bất kỳ nông dân nào bắt được cô.

Bessie không chắc về cơ hội thành công của mình, bởi điều đó phụ thuộc vào số nông dân mà lực lượng hành pháp có thể điều động. Biết Bessie xuất hiện tại chuồng \(K\), hãy giúp cô xác định số nông dân ít nhất cần có để bắt được cô, giả sử những người nông dân phân bố tối ưu giữa các chuồng là lối thoát.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(K\). Mỗi dòng trong \(N-1\) dòng tiếp theo chứa hai số nguyên, mỗi số thuộc khoảng \(1 \ldots N\), mô tả một đường hầm nối hai chuồng.

Dữ liệu ra

In ra số nông dân ít nhất cần có để đảm bảo bắt được Bessie.

Ví dụ

7 1
1 2
1 3
3 4
3 5
4 6
5 7

3

Nguồn

USACO 2018 January Contest, Gold — Cow at Large

Tác giả bài toán: Dhruv Rohatgi.

Bessie đang sở hữu một dải vải bạt dài \(N\) đơn vị (\(1 \leq N \leq 10^6\)) và cô muốn tô màu nó. Tuy nhiên, cô không thể kiếm được cọ vẽ. Thay vào đó, cô có \(M\) con dấu cao su mang các màu khác nhau (\(1 \leq M \leq 10^6\)), mỗi con dấu rộng \(K\) đơn vị (\(1 \leq K \leq 10^6\)). Kinh ngạc trước vô vàn khả năng trước mắt, cô muốn biết chính xác mình có thể tạo ra bao nhiêu bức tranh khác nhau bằng cách đóng các con dấu lên tấm vải theo một thứ tự nào đó.

Để sử dụng một con dấu, trước tiên phải căn nó khớp chính xác với \(K\) đơn vị liền kề trên tấm vải. Con dấu không được vượt ra ngoài hai đầu tấm vải và cũng không được phủ lên một phần lẻ của một đơn vị. Sau khi được đặt xuống, con dấu tô \(K\) đơn vị mà nó phủ bằng màu của mình. Mỗi con dấu có thể được sử dụng nhiều lần, đúng một lần hoặc hoàn toàn không được sử dụng. Tuy nhiên, khi Bessie hoàn tất, mọi đơn vị trên tấm vải đều phải được tô ít nhất một lần.

Hãy giúp Bessie tìm số bức tranh khác nhau mà cô có thể tô, lấy phần dư theo \(10^9+7\). Hai bức tranh trông giống hệt nhau nhưng được tạo bởi các chuỗi thao tác đóng dấu khác nhau vẫn được tính là cùng một bức tranh.

Phân nhóm

Trong ít nhất \(75\%\) số bộ dữ liệu vào, \(N,K \leq 10^3\).

Dữ liệu vào

Dòng duy nhất chứa ba số nguyên \(N\), \(M\) và \(K\). Dữ liệu đảm bảo \(K \leq N\).

Dữ liệu ra

In ra một số nguyên duy nhất: số bức tranh có thể tạo ra, lấy phần dư theo \(10^9+7\).

Ví dụ

3 2 2

6

Nguồn

USACO 2018 January Contest, Gold — Stamp Painting

Tác giả bài toán: Dhruv Rohatgi.