{"problem":{"name":"[CEOI 2009] Harbingers","description":{"content":"给定一颗树，树中每个结点有一个邮递员，每个邮递员要沿着唯一的路径走向 capital（$1$ 号结点），每到一个城市他可以有两种选择： 1. 继续走到下个城市； 2. 让这个城市的邮递员替他出发。 每个邮递员出发需要一个准备时间 $W_i$，他们的速度是 $V_i$，表示走一公里需要多少分钟。现在要你求出每个城市的邮递员到 capital 的最少时间（不一定是他自己到 capital，可以是别","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10602"},"statements":[{"statement_type":"Markdown","content":"给定一颗树，树中每个结点有一个邮递员，每个邮递员要沿着唯一的路径走向 capital（$1$ 号结点），每到一个城市他可以有两种选择：\n\n1. 继续走到下个城市；\n2. 让这个城市的邮递员替他出发。\n\n每个邮递员出发需要一个准备时间 $W_i$，他们的速度是 $V_i$，表示走一公里需要多少分钟。现在要你求出每个城市的邮递员到 capital 的最少时间（不一定是他自己到 capital，可以是别人帮他）？\n\n## Input\n\n第一行一个正整数 $N$；\n\n接下来 $N-1$ 行，每行三个正整数 $A,B,C$，表示结点 $A$ 和 $B$ 之间有一条长度为 $C$ 的边；\n\n再接下来 $N-1$ 行，每行 $2$ 个整数 $W_i,V_i$。\n\n## Output\n\n输出每个城市的邮递员到 capital 的最少时间。\n\n[samples]\n\n## Note\n\n对于 $20\\%$ 的数据，$N\\leq 2500$；\n\n对于 $50\\%$ 的数据，树是一条链；\n\n对于所有数据，$3\\leq N\\leq 10^5$，$0\\leq W_i,V_i\\leq 10^9$，每条边长度不超过 $10^4$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10602","tags":["动态规划 DP","2009","二分","O2优化","CEOI（中欧）","斜率优化","单调栈"],"sample_group":[["5\n1 2 20\n2 3 12\n2 4 1\n4 5 3\n26 9\n1 10\n500 2\n2 30","206 321 542 328"]],"created_at":"2026-03-03 11:09:25"}}