新型武器

【问题背景】

“嘿，亲爱的！”
天使轻轻的从天上落下来，黄昏的光晕柔柔地映在她半透明的翅膀上。

“看我给你弄到了什么！”
刚落到地上的天使轻轻一跃，扑入路霸的怀中。

“你看，这是我给你弄到的，智能分裂子弹。”
天使从她的包中掏出了一个黑色的小球。

“我知道你很喜欢的你那把爆裂枪，所以我让温斯顿把子弹做成了这个样子。”
拿过路霸手中的枪，天使把里面的各种碎片都倒了出来，从包里抓了一把子弹装了进去。

“你看，和以前一样。”
天使笑的很开心，落日在她的眼中熠熠生辉。

“不过以后你就要动些脑子了，这种子弹遇到路口就会分裂，然后沿着每个岔路继续飞行。”
一边说着，天使拉着路霸的手，带着他来到了训练场的边缘。

“你知道的，没有完全分裂的子弹实在没什么伤害，不过你可以设定你的子弹分裂几次。”
说着，天使朝前开了一枪，射出的子弹随即分裂，沿着前面几条岔路向前飞去，准确的击中了道路终点路口处的靶子。

“刚才我设定让它只分裂一次，所以才能命中那些靶子——因为那时它已经完全分裂了。分裂后的子弹再分裂的话，分裂次数是不加在一起的。”
凭空中出现了一个由蓝色激光构成的记分牌。

“我让秩序之光和Athena重新设计了这边的地形和程序，这样你就可以练习你的新武器了——你喜欢吗？”
天使伸出纤细的左手，轻抚着路霸的脸颊。

“这里的场地有许多的路口，还有很多道路把它们连了起来，它们形成了一棵树——我不确定是不是这个词的，Athena这么告诉我的。”
天使伸出两指向下一滑，一张地图显现在了空中。

“你看，就是这样。你可以站在一个路口，向着叶子的方向发射子弹——哦是的！这地图确实像是一颗生机盎然的树，还有叶子。Athena的比喻真是贴切！”
说着，天使朝着“叶子”的方向又开了一枪，子弹和上次一样击中那些靶子，积分版上跳出了应一个数字。

“每个路口的靶子上都有一个分数，完全分裂的子弹击中靶子，你就能得到那些分数了。”
天使指着远处的路口。

“嘿你知道吗？我很喜欢叶子的，在中国，有的叶子可以拿来治病，直接泡在水里喝掉就行——小美告诉我的，她懂得真多呀！”
地图上的路口处，上面显示的数字变了一下。

“我想你发现了，路口靶子上的分数是会变的，不过我会告诉你。”
天使把手中的爆裂枪还给了路霸，一跃而起，缓缓落在路霸的背上，轻轻环住了路霸的脖子。

“对你这么好，接下来来接受我的考验吧！~”

Mercy said.

【问题描述】

给一包含 N 个节点的树，以 1 号点为根。 求 u 号点的子树上，在子树中深度为 c 的点的权值和（u 号点深度为 0）。 包含权值修改操作。

【输入格式】

输入共 N+Q+2 行。

第 1 行包含 1 个正整数 N，表示共有 N 个节点。
第 2 行包含 N 个由空格隔开的非负的整数 V1, V2, V3 ... VN，其中 Vi 表示编号为 i 的点的权值。
第 2 +(1) 至 2 +(N-1) 行，每行包含 2 个正整数 fr，to，表示一边连接 fr，to 两点。
第 N+2 行包含 1 个正整数 Q，表示接下来共有 Q 个 修改 / 询问。
第 N+2 +(1) 至 N+2 +(Q) 行，每行包含 1 个 修改 / 询问。

修改 格式：
1 u v
表示将 u 号点的权值改为 v。

询问 格式：
2 u c 求 u 号点的子树上，在子树中深度为 c 的点的权值和（u 号点深度为 0）。

【输出格式】

输出多行（<= Q）。

每行包含 1 个非负的整数，表示其对应 询问 的答案，按照输入的先后顺序依次回答。

【样例输入】

7
1 1 1 1 1 1 1
1 2
1 3
2 7
3 4
3 6
4 5
7
2 1 1
2 1 2
2 3 6
1 4 5
2 4 0
2 1 2
2 3 1

【样例输出】

2
3
0
5
7
6

【数据规模与约定】

对于全部测试点：
编号为 1 的点是根; fa 是 to 的父亲节点; to > fa; to - fa <= 50
0 <= Vi <= 3000; 0 <= v <= 3000
c < N

【更多说明】

温斯顿的小课堂：
“帮路霸做的子弹能够飞的那么远，就是得益于它能分裂的特点，分裂时产生的能量使得它能飞向下一个路口。”
“所以，即使这个路口没有分叉，它也会分裂一次，对，就像运载火箭脱离一样。”

“Cheers love! 天使和路霸才不是CP，流言止于智者，恩。”