题目描述

小 C 是一名药师，为了制作出某种药剂，她需要在 S 大陆上寻找一些药材。

S 大陆可以抽象为一棵 $n$ 个顶点的无根树，每个顶点上都有一种药材。每种药材的属性可以描述为一个三元组 $(x,y,z)$，其中 $x$，$y$，$z$ 均为正整数。

如果小 C 获得了 $n$ 种属性分别为 $(x_1,y_1,z_1), (x_2,y_2,z_2) \ldots (x_n,y_n,z_n)$ 的 $n$ 种药材，她可以任取 $n$ 个不全为 $0$ 的非负实数 $a_1,a_2 \ldots a_n$，将这些药材调和为一种属性为 $(\sum a_i x_i,\sum a_i y_i,\sum a_i z_i)$ 的药剂。

现在小 C 需要在 S 大陆上收集药材。具体而言，她需要选定树上的一个连通块，并获得连通块中所有顶点上的药材。现给定小 C 想制作的药剂的属性 $(a,b,c)$，请你求出，如果小 C 需要使用所获得的药材调和出属性为 $(a,b,c)$ 的药剂，她选定的连通块的大小至少是多少。

输入格式

输入共 $2n$ 行。

第一行四个正整数 $n,a,b,c$。

接下来 $n$ 行，每行三个正整数 $x_i,y_i,z_i$，表示 $i$ 号节点上的药材的属性。

接下来 $n-1$ 行，每行两个整数 $u$ 和 $v$，表示树上存在一条连接 $u$ 和 $v$ 的边。

保证输入的边描述的是一棵树。

保证不存在两个完全相同的药材，但是可以存在某一个药材的属性和所需药剂完全一致。

保证对于所有药材，都有 $x_i + y_i + z_i = a + b + c$。

输出格式

输出一行一个整数，为所求答案。

4 2 2 3
1 1 5
3 2 2
3 3 1
2 4 1
1 2
2 3
2 4

3

8 3 269 1729
607 777 617
549 717 735
341 672 988
5 601 1395
846 263 892
796 954 251
243 144 1614
978 430 593
2 1
3 2
4 1
5 4
6 2
7 1
8 5

-1

提示

样例 1 解释

对于第一组样例，可以选择包含顶点 $1$，$2$ 和 $3$ 的连通块，取 $a_1,a_2,a_3$ 分别为 $\dfrac{1}{2},0,\dfrac{1}{2}$，即可得到属性为 $(\dfrac{1}{2} + \dfrac{3}{2},\dfrac{1}{2} + \dfrac{3}{2},\dfrac{5}{2} + \dfrac{1}{2}) = (2,2,3)$ 的药材。

子任务

对于所有测试数据，保证 $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 添加一组 hack 数据。