Площади и фонари

В Барселоне 15 века было $n$ площадей. Некоторые площади соединены двусторонней дорогой. Всего существует $n-1$ таких дорог, причем от каждой площади можно добраться до любой другой по этим дорогам, иначе говоря --- площади образуют дерево c $n$ вершинами.

На $i$-й площади находится $r\_i$ фонарей. Каллуму будет легче бороться с тамплиерами, если город будет более освещен. Поэтому он хочет включить на некоторых площадях фонари, причем чтобы $i$-я площадь была достаточно освещена, на ней должно быть включено не менее $l\_i$ фонарей.

Каллум называет площадь окраинной, если она соединена ровно одной дорогой с некоторой другой.

Каллум называет площадь $v$ яркой, если существует способ включить некоторое количество фонарей на каждой из площадей, чтобы все площади были достаточно освещены, и количество горящих фонарей на пути от площади $v$ до всех окраинных площадей неравных $v$, было одинаково.

Количество горящих фонарей на пути --- это суммарное количество горящих фонарей на всех площадях этого пути.

Помогите Каллуму определить, какие площади являются яркими.

В первой строке находится натуральное число $n$ --- количество площадей ($2 \le n \le 10^5$).

В следующих $n-1$ строках находится описание дорог между площадями: в $i$-й строке два натуральных числа $a\_i$ и $b\_i$ ($1 \le a\_i, b\_i \le n, a\_i \ne b\_i$) --- номера площадей, которые соединяет данная дорога.

В следующих $n$ строках находится описание фонарей на площадях: в $i$-й строке два неотрицательных целых числа $l\_i$ и $r\_i$ ($0 \le l\_i \le r\_i \le 10^4$) --- минимальное и максимальное количество фонарей, которые можно включить на $i$-й площади.

Гарантируется, что площади образуют дерево.

В единственной строке выведите $n$ чисел: $1$ если данная площадь является яркой, и $0$ иначе.