| 题目名称 | 3912. 苍天树 |
|---|---|
| 输入输出 | ether_tree.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 4000 ms (4 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 12 |
| 题目来源 |
 op_组撒头屯
于2023-09-03加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：1， 提交：1， 通过率：100% | ||||
 op_组撒头屯 |
100 | 5.536 s | 65.65 MiB | C++ |
| 本题关联比赛 | |||
| 2023级模拟测试1 | |||
| 关于 苍天树 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @YunQian :
byd spx能不能别玩Genshit了，差不多得了，cogs里也有你. jason
2023-10-18 17:28
3楼
| ||||
|
你说得对但是我今天抽温迪没歪
YunQian
2023-10-17 21:23
2楼
| ||||
|
op_组撒头屯
2023-09-06 18:32
1楼
| ||||
【题目背景】
“传说，飞鸟啄去了神像的眼瞳，然后散落到世界各地
当然了，这只是传说而已
不过，据说把散失的神瞳献给神像，会有好事发生呢”
【题目描述】
风起地有一颗大树名为苍天树，它由 $n$ 个节点组成，以 $1$ 号节点为根，$\mathrm{Venti}$ 初始时位于节点 $S$。
苍天树上会依次出现 $m$ 个风神瞳，第 $i$ 个风神瞳位于节点 $a_i$，$\mathrm{Venti}$ 需要 $b_i$ 的时间收集它。当且仅当一个风神瞳被收集后，下一个风神瞳才会立即出现。初始时，树上只有 $1$ 号风神瞳。
现在 $\mathrm{Venti}$ 要以最快的方式收集这些风神瞳。对于所有节点 $i$，你需要计算在他收集完毕之前，最后一次位于节点 $i$ 的时间。
【输入格式】
第一行包含三个正整数 $n,m,S$，分别表示节点数，风神瞳数，初始节点。
第二行包含 $2(n-1)$ 个正整数，每两个为一组，第 $i-1$ 组两个数 $f_i,w_i$ 分别表示 $i$ 节点的父节点和经过这条边的耗时。保证 $f_i \lt i$。
接下来 $m$ 行，每行包含两个正整数 $a_i,b_i$，表示一个风神瞳的位置和收集耗时。
【输出格式】
共 $n$ 个数，第 $i$ 个表示 $\mathrm{Venti}$ 最后一次位于节点 $i$ 的时间。若 $\mathrm{Venti}$ 未曾到达节点 $i$，输出 $-1$。
【样例输入】
7 4 3 1 4 2 5 2 1 2 3 1 2 6 6 6 10 4 1 4 3 3 5
【样例输出】
23 33 43 32 -1 21 -1
【数据规模与约定】
对于前 $50\%$ 的数据，$1 \le n,m \le 5 \times 10^3$。
对于 $100\%$ 的数据，$1 \le n,m \le 10^6$。
对于所有数据，$1 \le S,x,y,a_i \le n$，$1\le w,b_i \le 10^3$。
输入输出量较大，建议使用较快的输入输出方式。
【来源】
$rsr\;\;playing\;\; Genshin$