{"problem":{"name":"[PA 2022] Miny","description":{"content":"**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 4 [Miny](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/min/)** 给定一棵树（无向无环图），树上每条边有一个确定的长度。每个点上都有一颗地雷，每个地雷有一个确定的爆炸半径。如果一个地雷爆炸了，所有距离这颗","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":9000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9260"},"statements":[{"statement_type":"Markdown","content":"**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 4 [Miny](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/min/)**\n\n给定一棵树（无向无环图），树上每条边有一个确定的长度。每个点上都有一颗地雷，每个地雷有一个确定的爆炸半径。如果一个地雷爆炸了，所有距离这颗地雷不超过其爆炸半径的地雷都会爆炸。我们定义两个点之间的距离是这两个点之间简单路径上边的长度和。对于每颗地雷，如果手动引爆它，确定有多少地雷会爆炸。注意对于每颗地雷，我们认为手动引爆它与手动引爆其他地雷互相独立。\n\n## Input\n\n第一行包含一个整数 $n$，表示树的节点数（也是地雷个数）。树节点编号是从 $1$ 到 $n$ 的整数。\n\n第二行 $n$ 个整数 $r_1,r_2,\\ldots,r_n$，第 $i$ 个整数为位于节点 $i$ 的地雷的爆炸半径。\n\n接下来 $n-1$ 行，每行三个整数 $a_i,b_i,c_i$，表示一条长 $c_i$ 的边连接节点 $a_i$ 和 $b_i$。\n\n保证输入可以正确表示一棵树。\n\n## Output\n\n对于 $100\\%$ 的数据，满足：\n\n输出一行 $n$ 个整数，第 $i$ 个整数表示如果我们手动引爆在节点 $i$ 上的地雷，有多少地雷会爆炸。\n\n[samples]\n\n## Note\n\n$1\\le n\\le 10 ^ 5, 0\\le r_i\\le 10^{18}, 1\\le a_i,b_i\\le n,1\\le c_i\\le 10^{12}$","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9260","tags":["点分治","2022","拓扑排序","强连通分量","Tarjan","分块","线段树合并","PA（波兰）","bitset"],"sample_group":[["5\n8 1 0 4 6\n2 4 2\n3 1 9\n2 5 5\n2 1 2\n","4 1 1 4 2\n"]],"created_at":"2026-03-03 11:09:25"}}