苍天树

【题目背景】

【题目描述】

风起地有一颗大树名为苍天树，它由 $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$