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