[CEOI 2009] Harbingers

Luogu
IDLGP10602
Time1000ms
Memory512MB
DifficultyP6
动态规划 DP2009二分O2优化CEOI(中欧)斜率优化单调栈
给定一颗树,树中每个结点有一个邮递员,每个邮递员要沿着唯一的路径走向 capital($1$ 号结点),每到一个城市他可以有两种选择: 1. 继续走到下个城市; 2. 让这个城市的邮递员替他出发。 每个邮递员出发需要一个准备时间 $W_i$,他们的速度是 $V_i$,表示走一公里需要多少分钟。现在要你求出每个城市的邮递员到 capital 的最少时间(不一定是他自己到 capital,可以是别人帮他)? ## Input 第一行一个正整数 $N$; 接下来 $N-1$ 行,每行三个正整数 $A,B,C$,表示结点 $A$ 和 $B$ 之间有一条长度为 $C$ 的边; 再接下来 $N-1$ 行,每行 $2$ 个整数 $W_i,V_i$。 ## Output 输出每个城市的邮递员到 capital 的最少时间。 [samples] ## Note 对于 $20\%$ 的数据,$N\leq 2500$; 对于 $50\%$ 的数据,树是一条链; 对于所有数据,$3\leq N\leq 10^5$,$0\leq W_i,V_i\leq 10^9$,每条边长度不超过 $10^4$。
Samples
Input #1
5
1 2 20
2 3 12
2 4 1
4 5 3
26 9
1 10
500 2
2 30
Output #1
206 321 542 328
API Response (JSON)
{
  "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,可以是别...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments