世末农庄

Problem Description

西元????年，星球"泰拉"发生了核战争，整个地上世界成为了一片废土，由于辐射，异变生物已经占领了地上世界。 矮人族先西为了生存，不得不隐入地下进行生存。 幸好！先西的老祖宗早有远见，开发了地下农庄。地下农庄是一个家中地下室为根（记根的编号为 $0$）的树形结构，由于老祖宗没有留下地图，先西只能进行探索，以找寻农庄中每个农田的具体位置。 先西带着升降滑索和背包进入了农庄，并把锚点打在了家中的地下室。也就是说，它可以在回家时从当前所在位置到根的简单路径上获取农田中的农作物。 先西发现，不同农田的农作物所能提供的营养参差不齐，每单位农作物能得到的粮食不同。简单来说，某一层的粮食产出符合如下公式：

粮食重量=该田农作物的营养值p$\cdot$该田剩余农作物重量w 并且，越是到达深层，环境越是恶劣，农田的农作物营养值总是不如上一层直接相邻农田的营养值高。 此外，由于极少数异变蝗虫会钻地以获取食物，某些已经发现的农田可能因此被一扫而空。 为了简化问题，每天仅会发生下列三种事情之一： - 发现新的农田，编号记为 $u$，其与某一个已知的编号为 $v$ 的农田相通（注意地下农庄是一个树形结构），该农田农作物的营养值为 $p_u$，农作物重量为 $w_u$，且由于深处环境更加恶劣，总是有 $p_u < p_v$； - 回家整理行装，此时先西在编号为 $k$ 的农田，打算沿着最短路径回到地下室（根），背包还能装 $s$ 个单位重量的农作物，此时需要输出先西最多能得到多少粮食重量（先西总是优先保证这一天带走的农作物能够生产最多粮食），注意每次获取农作物后，农作物剩余量会减少； - 异变蝗虫入侵，此时编号为 $l$ 的农田中，农作物被一扫而空。 现在对于接下来 $q$ 天，根据已知的地下农庄结构，背包剩余重量空间，每次回家时先西应当如何决策以获得最多的粮食回到地下室？ **简单地说：** 初始有一棵只有根节点的树，根编号为 $0$，根有两个点权 $p_0$ 和 $w_0$； 在 $q$ 个操作中，每个操作是以下三种情况之一： - 操作1：新增一个未出现过的节点 $u$，令节点 $u$ 与某已经存在的节点 $v$ 相连，有两个点权 $p_u$ 和 $w_u$，保证 $p_u

第一行输入一个正整数 $T(1\leq T\leq 5)$，表示有 $T$ 组测试用例。对每组测试用例：

• 第一行，给出三个整数 $q$, $p_0$, $w_0$，以空格隔开，分别表示总天数，根节点农田农作物营养值，农作物重量。
• 接下来 $q$ 行，首先给出一个整数 $opt$，用于表示三种事情的编号，紧接一个空格，然后根据 $opt$ 的不同：
• 若 $opt=1$，则表示发现新的农田，接下来给出整数 $u,v, p_u, w_u$，同样以空格隔开，保证编号为 $u$ 的农田未被发现，而为 $v$ 的已被发现，且 $p_u < p_v$；
• 若 $opt=2$，则表示回家整理行装，接下来给出整数 $k, s$，同样以空格隔开，保证编号 $k$ 的农田已经被发现，此时需要进行输出，具体见“输出格式”节；
• 若 $opt=3$，则表示异变蝗虫入侵，接下来给出整数 $l$，同样保证编号 $l$ 的农田已经被发现。 对所有测试用例，$1 \leq q \leq 2 \times 10^5$，且 $1 \leq u \leq 2 \times 10^5$，$0 \leq v, k, l \leq 2 \times 10^5$，$p_i, w_i, s \leq 10^6, i \in \mathbb{N}$。

Output

对每组测试用例：若输入 $opt$ 为 $2$，则需要输出一行两个整数 $x, y$ （用空格隔开），分别表示背包中装入的农作物重量，以及能得到的粮食总量。

Sample Input

2
5 6 4
2 0 3
1 2 0 3 2
2 2 4
1 4 0 1 3
2 4 2
6 6 4
2 0 3
1 2 0 3 2
1 4 2 1 3
3 2
2 4 2
2 2 10

Sample Output

3 18
3 12
2 2
3 18
2 7
0 0

Hint

在样例的测试用例一中，一共有 $q=5$ 天，初始根节点 $p_0=6,w_0=4$.

• 第一天，用大小为 $s=3$ 的背包容量，拿走了 $0$ 号节点 $3$ 个单位重量的农作物，$w_0\to 1$，得到粮食总量是 $3\times 6=18$.
• 第二天，添加了一个 $2$ 号节点，连向 $0$ 号点，$p_2=3\lt p_0,w_2=2$.
• 第三天，用大小为 $s=4$ 的背包，在 $2$ 号点询问，拿走 $0$ 号点 $1$ 个单位重量的农作物，以及 $2$ 号点 $2$ 个单位重量的农作物，得到的总重量为 $1+2=3$，粮食总量是 $1\times 6+2\times 3=12$.
• $\dots$

Source

2024“钉耙编程”中国大学生算法设计超级联赛（5）