U93147 旅行诗（lyric）
题目描述
给你一颗有根树，每个节点有一个逃脱代价 $t_u$，每个节点到达自己的父亲有一个代价 $f_u$，到达自己的孩子 $v$ 有一个代价 $g_v$。
每次给你一个 $u, k$，询问从 $u$ 出发，如何选取一个节点 $v$，使得从 $u$ 到 $v$ 的路径上每个点都距离根节点的边数不低于 $k$，且到达该点的代价加上从该点逃脱的代价尽量小？你有非常多组询问，你只需要每次回答最小的总代价。
输入格式
第一行包含八个非负整数 $n, m, \mathrm{SA}, \mathrm{SB}, \mathrm{SC}, t_1, t_2$，其中 $n$ 表示树的节点数，$m$ 表示询问次数。
接下来一行输入 $n$ 个非负整数 $t_i$。
接下来 $n - 1$ 行，每行输入 $3$ 个整数 $p_i, f_i, g_i$，$i$ 从 $2$ 开始编号，$p_i$ 是 $i$ 的父亲节点，保证 $p_i < i$。
为了减少输入和输出量，询问和输出可以认为由以下代码接管，注意下文中的 `length[]` 数组意为：第 $i$ 项是 $i$ 节点到根节点经过的边数。你要解决询问的部分是其中的 `query()` 函数。你可以在主程序中处理完 `length[]` 数组后调用一次 `solve()` 函数。
```cpp
unsigned int SA, SB, SC;
int n, m, t1, t2;
unsigned int rng61() {
SA ^= SA > 5;
SA ^= SA
输出格式
由上文中的 `output` 变量给出输出。
说明/提示
#### 【样例 1 解释】
下面是本样例的实际每次询问和答案：
```plain
4 2
10
1 0
8
6 2
16
10 6
6
6 4
16
6 0
16
6 2
16
6 3
16
10 0
6
1 0
8
```
#### 【数据范围】
时间限制：$5\,\mathrm{s}$
空间限制：$512\,\mathrm{MB}$
对于 $100\%$ 的数据，$1\le n\le 3\times 10^5, 1\le m \le 6\times 10^6, 0\le t_1, t_2 \le 1$，输入的其余整数均在 $0$ 至 $10^9$ 之间。
对于 $0\%$ 的数据，保证 $m \le 5\times 10^7$。
| 测试点 | $n$ | $m$ | $t_1$ | $t_2$ |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| $1$ | $=10$ | $=n$ | $0$ | $0$ |
| $2$ | $=10$ | $=n$ | $0$ | $1$ |
| $3$ | $=10$ | $=n$ | $1$ | $0$ |
| $4$ | $=10$ | $=n$ | $1$ | $1$ |
| $5$ | $=10^2$ | $=n$ | $0$ | $0$ |
| $6$ | $=10^2$ | $=n$ | $0$ | $1$ |
| $7$ | $=10^2$ | $=n$ | $1$ | $0$ |
| $8$ | $=10^2$ | $=n$ | $1$ | $1$ |
| $9$ | $=3,000$ | $=n$ | $0$ | $0$ |
| $10$ | $=3,000$ | $=n$ | $0$ | $1$ |
| $11$ | $=3,000$ | $=n$ | $1$ | $0$ |
| $12$ | $=3,000$ | $=n$ | $1$ | $1$ |
| $13$ | $=10^5$ | $=n$ | $0$ | $0$ |
| $14$ | $=10^5$ | $=n$ | $0$ | $1$ |
| $15$ | $=10^5$ | $=n$ | $1$ | $0$ |
| $16$ | $=10^5$ | $=n$ | $1$ | $1$ |
| $17$ | $=3\times 10^5$ | $=n$ | $0$ | $0$ |
| $18$ | $=3\times 10^5$ | $=n$ | $0$ | $1$ |
| $19$ | $=3\times 10^5$ | $=2\times10^6$ | $1$ | $0$ |
| $20$ | $=3\times 10^5$ | $=2\times10^6$ | $1$ | $1$ |
| $21,22$ | $=3\times 10^5$ | $=2\times10^6$ | $0$ | $1$ |
| $23,24$ | $=3\times 10^5$ | $=6\times10^6$ | $0$ | $1$ |
| $25$ | $=3\times 10^5$ | $=6\times10^6$ | $1$ | $1$ |
#### 【提示】
本题时限会根据现场评测机进行调整，大约在标程（无读入优化等卡常）运行时间 $+ 1.5$ 秒左右。
本题提交程序禁止出现以 `#pragma` 为一行开头的代码。
#### 【故事】
那段童话般的时光，一带而过。兰长大了，世界变了。
总不能伪造空中楼阁吧？我不愿这么做，可是……事已至此，我必须让她见一见“新世界”。
茫然、惊愕。这是她第一次见到时的样子。尽管我们预演过千百遍。
成长？不，我不承认！为什么世界非得是这个样子？为什么世界要打碎每一个梦境？而我不得不放她去感受那份“无援和恐惧”？
饶了我吧，我可做不到还故作欣慰，或者大义凛然地说，这是什么“成长”。
我怕战争和仇恨的烈火熏坏她的双眼；
我怕愚昧的泥污感染她的清澈；
我怕世间的冰棱熄灭她的炽热。
她在原来的画室呆坐了一整天，呆呆地看着曾经绘制的星空。
第二天，她有一根头发白了。
“那些艺术……还有意义吗！”
是啊，画画是野蛮的，写诗是野蛮的。
我曾回答过她的十万个为什么。但今天我却不知答案。
或者说，我不知道该怎么回答，她。只好低着头，咬紧牙。
“……对不起。”
那座殿堂轰然倒塌了。如同泉涌。
天上的星星也在流血。
我要带着兰一同离开这个地方。
而离开的办法，只能从远古的符文中寻找答案。
远古魔法的符文系统十分复杂，它的字母种类数不胜数，时间紧迫，我不打算告诉这些细节了，我只会告诉你一颗有根树，你可以认为从根到一个节点的路径就代表着一个字符串。我随身携带的符文也可以用一个节点 $u$ 表示。树上每个节点都可以带我们离开，如果我现在持有的符文是节点 $u$ ，则需要消耗 $t_u$ 的时间用来发动。但是我持有的符文同时是可以修改的，这同样需要时间。我抹去符文的最后一个字，即从位于节点 $u$ 变成位于其父亲，这需要 $f_u$ 的时间，也可以变成位于其一个儿子 $v$，这需要 $g_v$ 的时间。
此外还有一个限制：在任何时候，我需保证字符串长度不能低于 $k$，字符串长度就是根节点到我所在节点经过的边数。
我想请你帮我的是，如何使用最短的时间完成逃离？我可能会给你多个问题，时间紧迫，请你尽快告诉我答案。
#### 【歌词】
在无趣人生之中，撞出水花，
在烟火虹霓之中，做梦想家，
逆光而来的剪影，心跳一霎，
——“ 那是你啊。”
在平淡际遇之中，时光发芽，
在空旷教室大喊，未曾声沙，
我眼中所有色彩，最明亮的，
——“只有你啊。”