5299. 路径查询（Path Queries）
时间限制：1500 MS 内存限制：512 MB
题目描述
## 题目描述 给定一棵包含 $n$ 个节点的根树。节点编号为 $1,2,\dots,n$，其中节点 $1$ 是根。每个节点都有一个值。 你的任务是处理以下两种类型的查询： 1. 将节点 $s$ 的值修改为 $x$； 2. 计算从根到节点 $s$ 的路径上**所有节点的值**的总和。 ## 输入格式 第一行输入两个整数 $n$ 和 $q$：节点数和查询数。节点编号为 $1,2,\dots,n$。 第二行包含 $n$ 个整数 $v1,v2,\dots,vn$：每个节点的初始值。 接下来有 $n-1$ 行描述边。 每行包含两个整数 $a$ 和 $b$：表示节点 $a$ 和 $b$ 之间有一条边。 最后有 $q$ 行描述查询。每个查询的形式为 "`1 s x`" 或 "`2 s`"。 ## 输出格式 输出每个类型为 $2$ 的查询的结果。 ## 输入输出样例 ### 输入 #1 ``` 5 3 4 2 5 2 1 1 2 1 3 3 4 3 5 2 4 1 3 2 2 4 ``` ### 输出 #1 ``` 11 8 ``` ### 输入 #2 ``` 11 3 3 1 2 4 1 7 3 3 1 1 4 1 2 1 3 2 4 2 5 3 6 3 7 6 8 6 9 9 10 9 11 2 3 1 3 5 2 6 ``` ### 输出 #2 ``` 5 15 ``` ## 说明/提示 ### 数据规模与约定 - $1\len,q\le2\cdot10^5$ - $1\lea,b,s\len$ - $1\levi,x\le10^9$