西元???? 年，星球”泰拉”发生了核战争，整个地上世界成为了一片废土，由于辐射，异变生
物已经占领了地上世界。
矮人族先西为了生存，不得不隐入地下进行生存。
幸好！先西的老祖宗早有远见，开发了地下农庄。地下农庄是一个家中地下室为根（记根的
编号为0）的树形结构，由于老祖宗没有留下地图，先西只能进行探索，以找寻农庄中每个农
田的具体位置。
先西带着升降滑索和背包进入了农庄，并把锚点打在了家中的地下室。也就是说，它可以在
回家时从当前所在位置到根的简单路径上获取农田中的农作物。
先西发现，不同农田的农作物所能提供的营养参差不齐，每单位农作物能得到的粮食不同。简
单来说，某一层的粮食产出符合如下公式：
粮食重量=该田农作物的营养值p·该田剩余农作物重量w
并且，越是到达深层，环境越是恶劣，农田的农作物营养值总是不如上一层直接相邻农田的
营养值高。
此外，由于极少数异变蝗虫会钻地以获取食物，某些已经发现的农田可能因此被一扫而空。
为了简化问题，每天仅会发生下列三种事情之一：
• 发现新的农田，编号记为u，其与某一个已知的编号为v的农田相通（注意地下农庄是
一个树形结构），该农田农作物的营养值为pu，农作物重量为wu，且由于深处环境更加
恶劣，总是有pu<pv；
• 回家整理行装，此时先西在编号为k的农田，打算沿着最短路径回到地下室（根），背
包还能装s个单位重量的农作物，此时需要输出先西最多能得到多少粮食重量（先西总
是优先保证这一天带走的农作物能够生产最多粮食），注意每次获取农作物后，农作物
剩余量会减少；
• 异变蝗虫入侵，此时编号为l的农田中，农作物被一扫而空。
现在对于接下来q天，根据已知的地下农庄结构，背包剩余重量空间，每次回家时先西应当
如何决策以获得最多的粮食回到地下室？
简单地说：
初始有一棵只有根节点的树，根编号为0，根有两个点权p0和w0；
在q 个操作中，每个操作是以下三种情况之一：
• 操作1：新增一个未出现过的节点u，令节点u与某已经存在的节点v相连，有两个点
权pu 和wu，保证pu<pv；
• 操作2：进行一次询问，给定节点k 和背包容量s，查询从节点k 到根的路径点集X
中，给每个点v∈X分配一个非负整数mv，在约束(∑mv≤s)∧(mv≤wv),v∈X 下，
得到Ans=max∑
v∈X(mv×pv)，输出 ∑mv 和 Ans，注意每次询问过后，需要进行更
新wv =wv−mv；
• 操作3：给定一个节点l，将wl 置为0.