Codeforces Round 851 (Div. 2) |
---|
Закончено |
Вам дано дерево с $$$n$$$ вершинами. Вершины пронумерованы от $$$1$$$ до $$$n$$$.
Вам нужно будет назначить каждому ребру вес. Пусть вес $$$i$$$-го ребра будет $$$a_i$$$ ($$$1 \leq i \leq n-1$$$). Вес каждого ребра должен быть целым числом от $$$0$$$ до $$$2^{30}-1$$$, включительно.
Вам дано $$$q$$$ условий. Каждое условие состоит из трех целых чисел $$$u$$$, $$$v$$$ и $$$x$$$. Это означает, что побитовое исключающее ИЛИ всех ребер на кратчайшем пути от $$$u$$$ до $$$v$$$ должно быть равно $$$x$$$.
Выясните, существуют ли числа $$$a_1, a_2, \ldots, a_{n-1}$$$, удовлетворяющие заданным условиям. Если существуют, выведите такое решение, при котором $$$a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$$$ будет наименьшим. Здесь $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.
Если существует несколько решений таких, что $$$a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$$$ является наименьшим, выведите любое из них.
Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$2 \le n \le 2.5 \cdot 10^5$$$, $$$0 \le q \le 2.5 \cdot 10^5$$$). В $$$i$$$-й из следующих $$$n-1$$$ строк содержится два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \neq y_i$$$), то есть $$$i$$$-е ребро соединяет вершины $$$x_i$$$ и $$$y_i$$$ в дереве.
Гарантируется, что заданные ребра образуют дерево.
Следующие $$$q$$$ строк содержат информацию об условиях.
Каждая строка содержит три целых числа $$$u$$$, $$$v$$$, $$$x$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$, $$$0 \le x \le 2^{30}-1$$$), означающие, что побитовое исключающее ИЛИ всех ребер на кратчайшем пути от $$$u$$$ до $$$v$$$ должно быть $$$x$$$.
Если не существует $$$a_1$$$, $$$a_2$$$, ..., $$$a_{n-1}$$$, которые удовлетворяют заданным условиям, выведите «No».
В противном случае в первой строке выведите «Yes».
Затем в следующей строке выведите $$$n-1$$$ целых чисел, где $$$i$$$-е целое число — это вес $$$i$$$-го ребра. Если существует несколько решений, то выведите такое решение, при котором $$$a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$$$ будет наименьшим.
Если существует несколько решений, при которых $$$a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$$$ принимает наименьшее значение, выведите любое.
При выводе «Yes» или «No» вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
4 4 1 2 2 3 3 4 1 4 3 2 4 2 1 3 1 2 3 1
No
6 2 1 2 2 3 3 4 2 5 5 6 1 4 2 2 6 7
Yes 4 2 4 1 6
6 2 1 2 2 3 3 4 2 5 5 6 1 4 3 1 6 5
Yes 6 1 4 3 0
Для первого примера не существует набора весов ребер, удовлетворяющего заданному условию.
Для второго примера два условия означают, что $$$a_1 \oplus a_2 \oplus a_3=2$$$ и $$$a_4 \oplus a_5=7$$$. Может существовать несколько решений, например, $$$(a_1, a_2, a_3, a_4, a_5)=(1, 2, 1, 4, 3)$$$.
Для третьего примера два условия означают, что $$$a_1 \oplus a_2 \oplus a_3=3$$$ и $$$a_1 \oplus a_4 \oplus a_5=5$$$. Существует множество решений, удовлетворяющих данному условию.
$$$(a_1, a_2, a_3, a_4, a_5)=(1, 1, 3, 4, 0)$$$ удовлетворяет заданным условиям, но побитовое исключающее ИЛИ весов всех ребер равно $$$7$$$, что не является наименьшим возможным значением $$$a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$$$, поэтому это не является верным решением.
Название |
---|