| Codeforces Round 572 (Div. 1) |
|---|
| Закончено |
Обратите внимание, что это первая задача из двух похожих задач. Вы можете взламывать эту задачу только тогда, когда решите обе задачи.
Вам дано дерево с $$$n$$$ вершинами. Изначально на каждом ребре написан $$$0$$$. За одну операцию вы можете выбрать любые $$$2$$$ различных листа $$$u$$$, $$$v$$$ и любое действительное число $$$x$$$, и прибавить $$$x$$$ ко всем числам записанных на ребрах на простом пути с $$$u$$$ до $$$v$$$.
Для примера на изображении ниже показан результат применения двух операций к графу: прибавления $$$2$$$ на пути от $$$7$$$ до $$$6$$$, а потом прибавления $$$-0.5$$$ на пути от $$$4$$$ до $$$5$$$.
Верно ли, что для любой конфигурации действительных чисел записанных на ребрах, мы можем достичь ее, выполнив конечное число операций?
Лист — это вершина степени $$$1$$$. Простой путь — это путь, не содержащий ни одну вершину дважды.
Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 10^5$$$) — количество вершин.
Каждая из следующих $$$n-1$$$ строк содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$), обозначающие что между вершинами $$$u$$$ и $$$v$$$ есть ребро. Гарантируется, что данные ребра образуют дерево.
Если существует конфигурация действительных чисел записанных на ребрах дерева, которой мы не можем достичь выполнением операций, выведите «NO».
Иначе выведите «YES».
Вы можете выводить каждую букву в любом регистре (строчную или заглавную).
2 1 2
YES
3 1 2 2 3
NO
5 1 2 1 3 1 4 2 5
NO
6 1 2 1 3 1 4 2 5 2 6
YES
В первом примере, мы можем прибавить любое действительное $$$x$$$ к числу записанному на единственному ребре $$$(1, 2)$$$.
Во втором примере одной из конфигураций, которые мы не можем достичь, является $$$0$$$ записанный на $$$(1, 2)$$$ и $$$1$$$ записанная на $$$(2, 3)$$$.
Ниже изображены графы с примеров $$$3$$$, $$$4$$$:
