3017: 普通计算姬

“奋战三星期，造台计算机”。小G响应号召，花了三小时造了台普通计算姬。

普通计算姬比普通计算机要厉害一些。普通计算机能计算数列区间和，而普通计算姬能计算树中子树和。更具体地，小G的计算姬可以解决这么个问题：

• 给定一棵 n 个节点的带权树，节点编号为 1 ∼ n，以 root 为根，设 sum_p 表示以点 p 为根的这棵子树中所有节点的权值和。

计算姬支持下列两种操作:

1 给定两个整数 u,v，修改点 u 的权值为 v。

2 给定两个整数 l,r，计算

尽管计算姬可以很快地完成这个问题，可是小G并不知道它的答案是否正确，你能帮助他吗？

第一行两个整数 n, m，表示树的节点数与操作次数。 接下来一行 n 个整数，第 i 个整数 di 表示点 i 的初始权值。 接下来 n 行每行两个整数 ai,bi，表示一条树上的边，若 ai = 0 则说明 bi 是根 root。 接下来 m 行每行三个整数，第一个整数 op 表示操作类型。 若 op = 1 则接下来两个整数 u,v 表示将点 u 的权值修改为 v。 若 op = 2 则接下来两个整数 l,r 表示询问 。

对每个操作类型 2 输出一行一个整数表示答案。

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

16
10
9