{"problem":{"name":"[湖北省选模拟 2023] 调和 / concoct","description":{"content":"小 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)$","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":4000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9544"},"statements":[{"statement_type":"Markdown","content":"小 C 是一名药师，为了制作出某种药剂，她需要在 S 大陆上寻找一些药材。\n\nS 大陆可以抽象为一棵 $n$ 个顶点的无根树，每个顶点上都有一种药材。每种药材的属性可以描述为一个三元组 $(x,y,z)$，其中 $x$，$y$，$z$ 均为正整数。\n\n如果小 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)$ 的药剂。\n\n现在小 C 需要在 S 大陆上收集药材。具体而言，她需要选定树上的一个连通块，并获得连通块中所有顶点上的药材。现给定小 C 想制作的药剂的属性 $(a,b,c)$，请你求出，如果小 C 需要使用所获得的药材调和出属性为 $(a,b,c)$ 的药剂，她选定的连通块的大小至少是多少。\n\n## Input\n\n输入共 $2n$ 行。\n\n第一行四个正整数 $n,a,b,c$。\n\n接下来 $n$ 行，每行三个正整数 $x_i,y_i,z_i$，表示 $i$ 号节点上的药材的属性。\n\n接下来 $n-1$ 行，每行两个整数 $u$ 和 $v$，表示树上存在一条连接 $u$ 和 $v$ 的边。\n\n**保证输入的边描述的是一棵树。**\n\n**保证不存在两个完全相同的药材，但是可以存在某一个药材的属性和所需药剂完全一致。**\n\n**保证对于所有药材，都有 $x_i + y_i + z_i = a + b + c$。**\n\n## Output\n\n输出一行一个整数，为所求答案。\n\n[samples]\n\n## Note\n\n### 样例 1 解释\n\n对于第一组样例，可以选择包含顶点 $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)$ 的药材。\n\n### 子任务\n\n对于所有测试数据，保证 $1 \\leq n \\leq 5 \\times 10^4$，$1 \\leq a,b,c,x_i,y_i,z_i \\leq 2 \\times 10^9$。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/qh0c3wfw.png)\n\n- 2023.8.25 添加一组 hack 数据。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9544","tags":["2023","O2优化","湖北"],"sample_group":[["4 2 2 3\n1 1 5\n3 2 2\n3 3 1\n2 4 1\n1 2\n2 3\n2 4\n","3"],["8 3 269 1729\n607 777 617\n549 717 735\n341 672 988\n5 601 1395\n846 263 892\n796 954 251\n243 144 1614\n978 430 593\n2 1\n3 2\n4 1\n5 4\n6 2\n7 1\n8 5\n","-1"]],"created_at":"2026-03-03 11:09:25"}}