BOI 2020 - Ngày 2

Cho một đồ thị vô hướng, trong đó mỗi cạnh có một trong hai màu: đen hoặc đỏ. Hãy gán một số thực cho mỗi đỉnh sao cho:

• Với mỗi cạnh đen, tổng hai số ở hai đầu mút bằng \(1\).
• Với mỗi cạnh đỏ, tổng hai số ở hai đầu mút bằng \(2\).
• Tổng giá trị tuyệt đối của tất cả các số được gán là nhỏ nhất có thể.

Nếu không thể gán các số thỏa mãn yêu cầu, hãy thông báo rằng không có cách gán hợp lệ.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), lần lượt là số đỉnh và số cạnh. Các đỉnh được đánh số bằng các số nguyên liên tiếp \(1,2,\ldots,N\).

\(M\) dòng tiếp theo mô tả các cạnh. Mỗi dòng chứa ba số nguyên \(a,b,c\), cho biết có một cạnh nối hai đỉnh \(a,b\) và có màu \(c\): \(1\) biểu thị màu đen, \(2\) biểu thị màu đỏ.

Dữ liệu ra

Nếu có lời giải, dòng đầu tiên in YES; dòng thứ hai in \(N\) số cách nhau bởi dấu cách. Số thứ \(i\) (\(1\le i\le N\)) là số được gán cho đỉnh \(i\).

Kết quả phải thỏa mãn:

• Tổng hai số ở hai đầu mút của mỗi cạnh sai khác với giá trị chính xác cần có một lượng nhỏ hơn \(10^{-6}\).
• Tổng giá trị tuyệt đối của tất cả các số được gán sai khác với giá trị nhỏ nhất có thể một lượng nhỏ hơn \(10^{-6}\).

Nếu có nhiều lời giải hợp lệ, có thể in bất kỳ lời giải nào.

Nếu không có lời giải, chỉ in một dòng chứa NO.

Ràng buộc

• \(1\le N\le100\,000\).
• \(0\le M\le200\,000\).
• \(1\le a,b\le N\), \(c\in\{1,2\}\).
• Không có điều kiện \(a\ne b\) hay điều kiện các cặp đầu mút phải khác nhau: đồ thị có thể có khuyên và nhiều cạnh nối cùng một cặp đỉnh.
• Giới hạn thời gian: \(0{,}7\) giây. Giới hạn bộ nhớ: \(256\) MiB.

Phân nhóm

1. \(5\) điểm: \(N\le5\), \(M\le14\).
2. \(12\) điểm: \(N\le100\).
3. \(17\) điểm: \(N\le1000\).
4. \(24\) điểm: \(N\le10\,000\).
5. \(42\) điểm: không có ràng buộc thêm.

Ví dụ

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

YES
0.5 0.5 1.5 -0.5

2 1
1 2 1

YES
0.3 0.7

3 2
1 2 2
2 3 2

YES
0 2 0

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

NO

Một ngôi làng có \(N\) ngôi nhà, mỗi nhà có đúng một người dân sinh sống. Các ngôi nhà được nối với nhau bằng những con đường. Mỗi con đường nối hai ngôi nhà và dài đúng \(1\) kilômét. Từ bất kỳ ngôi nhà nào cũng có thể đến bất kỳ ngôi nhà nào khác qua một hoặc nhiều con đường liên tiếp. Trong làng có tổng cộng \(N-1\) con đường.

Một ngày nọ, tất cả người dân quyết định chuyển sang nhà khác. Sau khi chuyển, mỗi ngôi nhà vẫn phải có đúng một người ở, nhưng không ai được ở lại ngôi nhà cũ của mình. Ta muốn biết giá trị nhỏ nhất và lớn nhất có thể của tổng độ dài các đường đi ngắn nhất từ nhà cũ đến nhà mới của tất cả người dân, tính bằng kilômét.

Hãy viết chương trình tìm cả hai giá trị này và đưa ra một cách phân nhà mới tương ứng cho mỗi trường hợp. Ngôi làng có bảy ngôi nhà minh họa ở Hình 1 và hai cách chuyển nhà được trình bày trong phần giải thích Ví dụ 2.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\). Các ngôi nhà được đánh số bằng các số nguyên liên tiếp \(1,2,\ldots,N\).

\(N-1\) dòng tiếp theo mô tả các con đường. Mỗi dòng chứa hai số nguyên \(a,b\), cho biết có một con đường nối hai ngôi nhà \(a\) và \(b\).

Dữ liệu ra

Dòng đầu tiên chứa hai số nguyên cách nhau bởi dấu cách: giá trị nhỏ nhất và lớn nhất của tổng độ dài các đường đi ngắn nhất, tính bằng kilômét.

Dòng thứ hai mô tả một cách phân nhà mới hợp lệ đạt tổng độ dài nhỏ nhất: \(N\) số nguyên đôi một khác nhau \(v_1,v_2,\ldots,v_N\), cách nhau bởi dấu cách. Với mỗi \(i\), \(v_i\) là số hiệu ngôi nhà mà người dân ban đầu ở nhà \(i\) sẽ chuyển đến, và \(v_i\ne i\). Nếu có nhiều cách hợp lệ, có thể in bất kỳ cách nào.

Dòng thứ ba mô tả một cách phân nhà mới hợp lệ đạt tổng độ dài lớn nhất, theo cùng định dạng.

Ràng buộc

• \(1<N\le10^5\).
• \(1\le a,b\le N\), \(a\ne b\).
• Có đúng \(N-1\) con đường, mỗi con đường dài \(1\) kilômét; từ mỗi ngôi nhà đều có thể đi đến mọi ngôi nhà khác.
• Giới hạn thời gian: \(0{,}7\) giây. Giới hạn bộ nhớ: \(256\) MiB.

Phân nhóm

1. \(12\) điểm: \(N\le10\).
2. \(38\) điểm: \(N\le1000\).
3. \(50\) điểm: không có ràng buộc thêm.

Bạn được \(50\%\) số điểm nếu, với mỗi bộ dữ liệu, kết quả chứa đúng tổng độ dài và một cách phân nhà hợp lệ cho một trong hai trường hợp: tổng độ dài nhỏ nhất hoặc tổng độ dài lớn nhất. Tuy nhiên, vẫn phải in phần mô tả cho cả hai trường hợp, mỗi phần gồm \(N\) số nguyên trong đoạn từ \(1\) đến \(N\), cách nhau bởi dấu cách. Đối với trường hợp có thể không đúng, các số này có thể là bất kỳ giá trị nào trong đoạn đó, chẳng hạn đều bằng \(1\).

Ví dụ

4
1 2
2 3
3 4

4 8
2 1 4 3
4 3 2 1

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

8 18
6 4 1 2 7 3 5
7 3 4 1 2 5 6

Ủy ban Nghiên cứu Virus Nhị phân đã phát hiện một cơ chế nhân bản của một họ virus lớn có mã di truyền là các dãy số \(0\) và \(1\). Mỗi virus bắt nguồn từ một gen duy nhất; để đơn giản, các gen được ký hiệu bằng các số nguyên từ \(0\) đến \(G-1\). Tại mỗi thời điểm, một virus là một dãy gen. Khi xảy ra đột biến, một gen trong dãy được thay bằng một dãy gen xác định theo bảng đột biến. Virus ngừng đột biến khi nó chỉ còn chứa các gen \(0\) và \(1\).

Chẳng hạn, xét bảng đột biến sau:

Một virus ban đầu chỉ gồm gen \(4\) có thể đột biến như sau. Phần được gạch dưới là dãy gen vừa được thay vào:

Hoặc virus có thể đột biến theo một cách khác:

Các kháng thể phát hiện virus bằng cách nhận ra sự xuất hiện của những đoạn liên tiếp nhất định gồm các số \(0\) và \(1\) trong mã của virus. Ví dụ, kháng thể phản ứng với đoạn \(\langle0\ 0\ 1\ 0\ 0\rangle\) sẽ phát hiện virus \(\langle0\ 0\ 1\ 0\ 0\ 1\ 0\ 1\rangle\), nhưng không phát hiện virus \(\langle0\ 1\ 0\ 1\ 0\ 0\ 1\ 0\ 1\rangle\).

Với mỗi gen từ \(2\) đến \(G-1\), các nhà khoa học muốn biết liệu tập kháng thể cho trước có đủ để phát hiện tất cả các virus có thể hình thành qua đột biến từ gen đó hay không. Nếu không, họ muốn biết độ dài của virus ngắn nhất không thể bị phát hiện.

Đôi khi các nhà khoa học không có kháng thể nào. Khi đó, hiển nhiên không virus nào có thể bị phát hiện, nên họ chỉ quan tâm đến độ dài của virus ngắn nhất có thể hình thành từ quá trình đột biến của gen đang xét.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(G,N,M\), lần lượt là số gen, số dòng trong bảng đột biến và số kháng thể.

\(N\) dòng tiếp theo mô tả bảng đột biến. Mỗi dòng bắt đầu bằng hai số nguyên \(a,k\), tiếp theo là một dãy gồm \(k\) số nguyên \(b_1,b_2,\ldots,b_k\), biểu diễn quy tắc:

Mỗi số nguyên từ \(2\) đến \(G-1\) xuất hiện ít nhất một lần với vai trò \(a\) trong bảng.

\(M\) dòng tiếp theo mô tả các kháng thể. Mỗi dòng bắt đầu bằng số nguyên \(\ell\), tiếp theo là dãy gồm \(\ell\) số nguyên \(c_1,c_2,\ldots,c_\ell\), mô tả đoạn mã mà kháng thể nhận ra.

Dữ liệu ra

In đúng \(G-2\) dòng, lần lượt là đáp án cho các gen từ \(2\) đến \(G-1\).

Nếu mọi virus có thể hình thành qua đột biến từ gen đang xét đều bị phát hiện bởi tập kháng thể đã cho, in YES. Cũng in YES nếu không có virus nào có thể hình thành từ gen đó, tức là các dãy không bao giờ ngừng đột biến để trở thành một dãy chỉ gồm \(0\) và \(1\).

Ngược lại, in NO, theo sau bởi một số nguyên là độ dài nhỏ nhất của một virus không thể bị phát hiện. Trong mọi bộ dữ liệu, giá trị này được bảo đảm nhỏ hơn \(2^{63}\).

Ràng buộc

• \(G>2\), \(N\ge G-2\), \(M\ge0\).
• Với mỗi dòng của bảng đột biến: \(2\le a<G\), \(k\ge1\), \(0\le b_i<G\) với mọi \(1\le i\le k\).
• Tổng tất cả các giá trị \(k\) không vượt quá \(100\).
• Mỗi gen từ \(2\) đến \(G-1\) xuất hiện ít nhất một lần ở vế trái của một quy tắc đột biến.
• Với mỗi kháng thể: \(\ell\ge1\), \(0\le c_i\le1\) với mọi \(1\le i\le\ell\).
• Tổng tất cả các giá trị \(\ell\) không vượt quá \(50\).
• Mọi giá trị số trong đầu vào đều là số nguyên.
• Độ dài nhỏ nhất cần in, nếu tồn tại, nhỏ hơn \(2^{63}\).
• Giới hạn thời gian: \(0{,}7\) giây. Giới hạn bộ nhớ: \(256\) MiB.

Phân nhóm

1. \(11\) điểm: không có kháng thể, tức \(M=0\).
2. \(14\) điểm: \(N=G-2\).
3. \(25\) điểm: có đúng một kháng thể, tức \(M=1\).
4. \(32\) điểm: tổng tất cả các giá trị \(\ell\) không vượt quá \(10\).
5. \(18\) điểm: không có ràng buộc thêm.

Ví dụ

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

NO 2
NO 4
NO 9
YES