laoya 的有根树
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给你一棵以 1 为根的带权有根树，最开始只有 1 号节点，定义 g(i) 为以 i 为根的子树的子树的总重量，定义 idx=1。可以进行三种操作：

操作1：`1 x w` 增加一个叶子节点，其编号为 idx+1，其父亲为 x，权值为 w，操作结束后 idx=idx+1

操作2：`2 x` 删除一个叶子节点，保证 x 为叶子节点，且删除的叶子节点不会为 1

操作3：`3 x` 查询当前树下，以 x 为根的子树中，任选两个节点 i 和 j (i \neq j)，使得g(i)*g(j)最大，若找不到两个节点，则输出 -1

输入描述:

第一行输入 m (1 \le m \le 300000)，val，分别代表总操作次数和 1 号点的权值

接下来 m 行每行先输入一个整数 op (1 \le op \le 3)，代表操作的类型，与题目描述中保持一致

若 op 为 1，则输入 x w，保证 (-10^4 \le w \le 10^4) 且 x 号节点未被删除

若 op 为 2，则输入 x，（保证x为叶子节点）

若 op 为 3，则输入 x ，（保证x号节点一定未被删除）

输出描述:

对于每个 op=3，输出最大的 g(i) \times g(j) 且 i \neq j
示例1

输入

复制 
7 -1
1 1 -1
1 1 -2
1 2 0
1 2 1
1 3 2
2 5
3 1

输出

复制 
2

说明

蓝色数字表示节点的重量，红色数字表示以它为根的子树的重量前 5 个操作后图上，第 6 个操作把 5 号节点删除，第 7 个操作时，g(1)=-2,~g(2)=-1,~g(3)=0,~g(4)=0,~g(5)=2
则最大的答案为 g(1)*g(2)=2。