Squares and Lanterns

In 15th-century Barcelona there were $n$ squares. Some squares are connected by two-way roads. There are $n-1$ roads in total, and from every square you can reach every other square along these roads, so the squares form a tree with $n$ vertices.

Square $i$ has $r_i$ lanterns. Callum will find it easier to fight the Templars if the city is better lit, so he wants to switch on some lanterns in some squares. Square $i$ is lit well enough only if at least $l_i$ lanterns are on there.

Callum calls a square peripheral if it is connected by exactly one road to another square.

Callum calls a square $v$ bright if there is a way to switch on some lanterns in each square so that every square is lit well enough, and the number of lit lanterns on the path from $v$ to every peripheral square other than $v$ is the same.

The number of lit lanterns on a path is the total number of lit lanterns on all squares of that path.

Help Callum determine which squares are bright.

The first line contains a natural number $n$ (the number of squares), with $2 \le n \le 10^5$.

Each of the next $n-1$ lines contains two natural numbers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$), the numbers of the squares connected by the road.

Each of the next $n$ lines contains two non-negative integers $l_i$ and $r_i$ ($0 \le l_i \le r_i \le 10^4$), the minimum and maximum number of lanterns that can be switched on in square $i$.

It is guaranteed that the squares form a tree.

Print $n$ numbers on one line. Print 1 if square $i$ is bright, and 0 otherwise.