Codeforces Round 395 (Div. 1) |
---|
Закончено |
Каждый Новый Год Тимофей и его друзья рубят в лесу дерево из n вершин и приносят его домой. Чтобы получше его украсить, они превращают его в березу. Береза — дерево из n вершин, каждая вершина i которого покрашена в какой-то цвет ci.
Но вот настал день рождения, и мама Тимофея попросила его вынести березу. Тимофей выносит березу так: хватает за какую-то вершину, остальные вершины опускаются вниз, и дерево становится подвешенным за вершину, за которую он схватил. После этого он идет с ним на улицу и выкидывает.
Попытавшись ухватить березу, Тимофей понял, что его раздражают разноцветные переливы. Поддерево раздражает Тимофея, если в нем есть вершины разных цветов. Он хочет найти, за какую вершину ему нужно взяться, чтобы ни одно поддерево не раздражало его. При этом он не рассматривает все дерево целиком как поддерево, потому что он не видит цвет корневой вершины.
Поддерево некоторой вершины — это подграф, содержащий эту вершину и всех ее потомков.
Определите, есть ли вершина, схватившись за которую, Тимофей не будет раздражен.
Первая строка содержит одно натуральное число n (2 ≤ n ≤ 105) — количество вершин в дереве.
Каждая из следующих n - 1 строк содержит два натуральных числа u и v (1 ≤ u, v ≤ n, u ≠ v), означающие, что существует ребро между вершинами u и v. Гарантируется, что данный граф является деревом.
В следующей строке содержатся n натуральных чисел c1, c2, ..., cn (1 ≤ ci ≤ 105), задающих цвета вершин.
В первой строке выведите «NO», если Тимофей не может взять березу так, чтобы его ничто не раздражало.
В противном случае выведите «YES», а в следующей строке выведите номер вершины, за которую Тимофею нужно схватить березу. Если существует несколько ответов, выведите любой.
4
1 2
2 3
3 4
1 2 1 1
YES
2
3
1 2
2 3
1 2 3
YES
2
4
1 2
2 3
3 4
1 2 1 2
NO
Название |
---|