Bedao Regular Contest 08 - KINGDOM

View as PDF

Submit solution


Points: 0.50 (partial)
Time limit: 2.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Ở một vương quốc độc tài nọ, vị vua anh minh Trí Fang từ lâu đã được biết đến với khả năng thao túng kẻ địch bằng những chiến thuật phòng thủ tài ba của mình.

Vào một ngày nọ, Trí quyết định rà soát khả năng phòng thủ của vương quốc của cậu ấy.

Vương quốc Trí Fang bao gồm ~n~ thành trì quan trọng được kết nối với nhau bởi ~n-1~ con đường hai chiều. Những con đường này đảm bảo rằng bất kỳ ~2~ thành trì nào cũng có thể đi đến được nhau.

Thành trì ~i~ có chỉ số chiến thuật là ~c_i~. Để vương quốc của cậu ấy an toàn, Trí phải đảm bảo rằng, với bất kì ~1~ thành trì nào bị chiếm đóng, trong ~n-1~ thành trị còn lại, những thành trì có thể đến được nhau phải có cùng chỉ số chiến thuật. Biết rằng nếu ~1~ thành trì bị chiếm đóng thì những con đường nối với thành trì đó sẽ không thể sử dụng được.

Trí muốn biết rằng với mỗi thành trì ~i~, nếu thành trì này bị chiếm đóng, ~n-1~ thành trì còn lại, những thành trì có thể đến được nhau có cùng một chỉ số chiến thuật hay không. Là một thần dân trung thành của Trí Fang, bạn hãy giúp vị vua kính mến của chúng ta tìm ra những thành trì ~i~ thỏa mãn.

Input

  • Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^{6})~.
  • ~n-1~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên ~u, v~ ~(1 \le u,v \le n)~ thể hiện có con đường hai chiều nối thành trì ~u~ và ~v~.
  • Dòng cuối cùng chứa ~n~ số nguyên ~c_1, c_2, \dots, c_n~ ~(1 \le c_i \le 2\times 10^{6}, 1 \leq i \leq n)~.

Output

  • Nếu không tồn tại thành trì ~i~ nào thỏa mãn nếu thành trì này bị chiếm đóng, ~n-1~ thành trì còn lại, những thành trì có thể đến được nhau phải có cùng một chỉ số chiến thuật, thì in ra NO trên một dòng duy nhất. Ngược lại, in ra YES ở dòng đầu tiên, dòng thứ hai in ra danh sách tăng dần các thành trì thỏa mãn.

Subtask

  • Subtask ~1~ (~20\%~ số điểm): ~1 \le n \le 5000~.
  • Subtask ~2~ (~20\%~ số điểm): Mỗi thành trì nối trực tiếp với tối đa ~2~ thành trì khác.
  • Subtask ~3~ (~20\%~ số điểm): ~1 \le n \le 2\times 10^{5}~.
  • Subtask ~4~ (~40\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

4
1 2
2 3
3 4
1 2 1 1

Sample Output 1

YES
2 

Sample Input 2

4
1 2
2 3
3 4
1 2 1 2

Sample Output 2

NO

Comments

Please read the guidelines before commenting.



  • 11
    K24PADuc   commented on Aug. 15, 2022, 11:57 p.m. edited

    Bài tương tự: https://codeforces.com/contest/763/problem/A