P9544 [Hubei NOI Qualifier Mock 2023] Harmonize / concoct

Xiao C is a pharmacist. To make a certain potion, she needs to find some herbs on the S Continent. The S Continent can be modeled as an unrooted tree with $n$ vertices, and each vertex has one kind of herb. The property of each herb can be described by a triple $(x,y,z)$, where $x$, $y$, and $z$ are all positive integers. If Xiao C obtains $n$ herbs with properties $(x_1,y_1,z_1), (x_2,y_2,z_2) \ldots (x_n,y_n,z_n)$, she may choose any $n$ non-negative real numbers $a_1,a_2 \ldots a_n$ that are not all $0$, and harmonize these herbs into a potion with properties $(\sum a_i x_i,\sum a_i y_i,\sum a_i z_i)$. Now Xiao C needs to collect herbs on the S Continent. Specifically, she needs to choose a connected subgraph (a connected block) on the tree, and obtain all herbs on the vertices inside it. Given the desired potion property $(a,b,c)$, please find the minimum possible size of the connected block such that Xiao C can use the obtained herbs to harmonize a potion with property $(a,b,c)$.

The input has $2n$ lines. The first line contains four positive integers $n,a,b,c$. The next $n$ lines each contain three positive integers $x_i,y_i,z_i$, representing the properties of the herb on node $i$. The next $n-1$ lines each contain two integers $u$ and $v$, indicating that there is an edge connecting $u$ and $v$ in the tree. **It is guaranteed that the given edges form a tree.** **It is guaranteed that there are no two completely identical herbs, but it is allowed that some herb has exactly the same property as the required potion.** **It is guaranteed that for all herbs, $x_i + y_i + z_i = a + b + c$.**

Output one integer in a single line, the required answer.

### Sample 1 Explanation For the first sample, you can choose the connected block containing vertices $1$, $2$, and $3$, and take $a_1,a_2,a_3$ as $\dfrac{1}{2},0,\dfrac{1}{2}$ respectively. Then you can obtain a potion with properties $(\dfrac{1}{2} + \dfrac{3}{2},\dfrac{1}{2} + \dfrac{3}{2},\dfrac{5}{2} + \dfrac{1}{2}) = (2,2,3)$. ### Subtasks For all testdata, it is guaranteed that $1 \leq n \leq 5 \times 10^4$, $1 \leq a,b,c,x_i,y_i,z_i \leq 2 \times 10^9$.  - 2023.8.25 Added one set of hack data. Translated by ChatGPT 5