USACO 2023 - Tháng 12 - Hạng Bạch Kim

Anh nông dân John có \(N\) con bò được đánh số từ \(1\) đến \(N\) và các mối quan hệ thân thiết của những con bò này được mô tả bởi một cây. Vào một hôm, thật không may khi có một dịch bệnh đang lan truyền khắp nơi quanh đó.

Vào ngày đầu tiên, một số con bò đã bị bệnh. Sau mỗi đêm, mỗi con bò đã bị lây nhiễm sẽ lây bệnh cho các con bò mà chúng thân thiết. Một khi con bò đã bị nhiễm bệnh thì con bò đó sẽ không khỏi bệnh. Sau vài đêm, John đã bắt đầu nhận ra vấn đề, vì vậy anh ấy sẽ kiểm tra những con bò của mình để xem những con nào bị mắc bệnh.

Bạn nhận được \(Q\) giá trị khác nhau mô tả số lượng đêm từ ngày đầu tiên đến ngày John kiểm tra đàn bò, các giá trị đó nằm trong đoạn \([0, N]\). Với mỗi số lượng đêm, hãy tìm số lượng tối thiểu các con bò bị nhiễm bệnh vào ngày đầu tiên, hoặc cho biết số lượng đêm đó không tồn tại so với thông tin mà John kiểm tra từ đàn bò của mình.

Input

• Dòng thứ nhất chứa một số nguyên \(N\) \((2 \le N \le 10^5)\) mô tả số lượng con bò.
• Dòng tiếp theo chứa một xâu nhị phân \(S\) độ dài \(N\), với \(S_i\) (\(S_i\) là kí tự thứ \(i\) của xâu \(S\), \(i \in [1, N]\)) là \(1\) nếu con bò thứ \(i\) bị bệnh vào ngày John kiểm tra hoặc \(0\) trong trường hợp ngược lại.
• \(N - 1\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên \(u, v\) mô tả 2 con bò thứ \(u\) và \(v\) quen biết nhau.
• Dòng tiếp theo gồm số nguyên \(Q\) \((1 \le Q \le 20)\) mô tả số lượng truy vấn.
• \(Q\) Dòng cuối cùng, dòng thứ \(j\) gồm số nguyên \(x_j\) mô tả số lượng đêm trước ngày John kiểm tra.

Output

• In ra \(Q\) dòng, dòng thứ \(j\) hãy in ra số lượng con bò bị nhiễm bệnh ở ngày đầu tiên, nếu không có trường hợp nào khả thi, hãy in ra \(-1\).

Scoring

• Subtask 1: \(N \le 10\).
• Subtask 2: Tất cả các con bò đều bị lây nhiễm bệnh.
• Subtask 3: \(N \le 400\).
• Subtask 4: Không có giới hạn gì thêm.

Example

5
11111
1 2
2 3
3 4
4 5
6
5
4
3
2
1
0

1
1
1
1
2
5

10
1111111111
1 2
2 3
2 4
2 5
2 6
6 7
7 8
8 9
9 10
11
0
1
2
3
4
5
6
7
8
9
10

10
3
2
1
1
1
1
1
1
1
1

5
11100
1 2
2 3
3 4
4 5
6
0
1
2
3
4
5

3
1
1
-1
-1
-1

Để cải thiện kiến thức toán học của mình, Bessie đã tham gia khóa học lý thuyết đồ thị và gặp khó khăn với bài toán sau. Hãy giúp cô ấy!

Bạn nhận được đồ thị vô hướng liên thông với các đỉnh được đánh số từ \(1\) đến \(N\) và các cạnh được đánh số từ \(1\) đến \(M\). Với mỗi đỉnh \(v\) trên đồ thị, ta sẽ thực hiện các thao tác sau theo thứ tự:

1. Cho tập \(S = \{v\}\) và giá trị \(h = 0\).
2. Trong khi \(|S|\)(số lượng phần tử của tập \(S\)) \(< N\):
   2.1. Chọn cạnh \(e\) có chỉ số nhỏ nhất sao cho có chính xác một đầu mút của cạnh \(e\) thuộc tập \(S\).
   2.2. Thêm đầu mút còn lại của cạnh \(e\) (điểm không thuộc \(S\)) vào tập \(S\).
   2.3. Cập nhập \(h = 10h + e\)
   (Nếu \(|S| < N\) thì quay về bước 2)
3. Trả về giá trị \(h\) (mod \(10^9 + 7\)).

Hãy xác định tất cả giá trị trả về của mỗi đỉnh sau khi thực hiện các thao tác trên.

Input

• Dòng đầu tiên chứa 2 số nguyên \(N\) và \(M\) mô tả số lượng đỉnh và số lượng cạnh \((2 \le N \le 2 \times 10^5, N−1 \le M \le 4 \times 10^5)\).
• Tiếp theo là \(M\) dòng, dòng thứ \(e^{th}\) chứa hai điểm đầu mút \((a_e, b_e)\) mô tả cạnh thứ \(e^{th}\) của đồ thị \((1 \le a_e < b_e \le N)\). Dữ liệu đảm bảo tất cả các cạnh đã cho tạo thành một đồ thị liên thông, và có tối đa một cạnh nối giữa 2 đỉnh bất kỳ.

Output

• In ra \(N\) dòng, dòng thứ \(i\) chứa giá trị trả về của quá trình bắt đầu từ đỉnh \(i\).
• Lưu ý rằng bạn cần xuất các kết quả theo modulo 10⁹ + 7.

Scoring

• Subtask 1: \(N, M \le 2000\)
• Subtask 2: \(N \le 2000\)
• Subtask 3: \(N \le 10000\)
• Subtask 4: \(a_e + 1 = b_e\) cho tất cả \(e\)
• Subtask 5: Không có ràng buộc bổ sung.

Example

3 2
1 2
2 3

12
12
21

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

1325
1325
2315
2315
5132

15 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15

678925929
678925929
678862929
678787329
678709839
678632097
178554320
218476543
321398766
431520989
542453212
653475435
764507558
875540761
986574081

Bessie đã nhận công việc điều phối tàu! Có hai ga tàu là A và B. Do hạn chế về ngân sách, chỉ có một đường ray nối hai ga. Nếu một đoàn tàu khởi hành từ một ga vào thời điểm \(t\), thì nó sẽ đến ga còn lại vào thời điểm \(t+T\).

Có \(N\) đoàn tàu cần lên lịch khởi hành. Tàu thứ i phải rời ga si vào thời điểm ti hoặc muộn hơn \((s_i \in \{A, B\}\). Không được phép có hai tàu di chuyển ngược chiều cùng lúc trên đường ray (vì chúng sẽ đâm vào nhau). Tuy nhiên, có thể có nhiều tàu di chuyển cùng chiều trên đường ray cùng lúc (giả sử các tàu có kích thước nhỏ không đáng kể).

Hãy giúp Bessie lên lịch khởi hành cho tất cả các đoàn tàu sao cho không có va chạm và tổng độ trễ được giảm thiểu. Nếu tàu thứ \(i\) khởi hành vào thời điểm \(a_i \ge t_i\), tổng độ trễ được tính là \(\Sigma_{i = 1}^{N}(a_i − t_i)\).

Input

• Dòng đầu tiên chứa \(N\) và \(T\) \((1 \le N \le 5000; 1 \le T \le 10^{12})\).
• \(N\) dòng tiếp theo, mỗi dòng chứa ga \(s_i\) và thời gian \(t_i\) \((0 \le t_i \le 10^{12})\) của tàu thứ \(i\).

Output

• In ra tổng độ trễ tối thiểu có thể xảy ra.

Scoring

• Subtask 1: \(N \le 15\)
• Subtask 2: \(N \le 100\)
• Subtask 3: \(N \le 500\)
• Subtask 4: \(N \le 2000\)
• Subtask 5: Không có ràng buộc bổ sung.

Example

1 95
B 63

0

4 1
B 3
B 2
A 1
A 3

1

4 10
A 1
B 2
A 3
A 21

13

8 125000000000
B 17108575619
B 57117098303
A 42515717584
B 26473500855
A 108514697534
B 110763448122
B 117731666682
A 29117227954

548047356974