[GXPC-S 2025] 花 / flower

小明在放学路上发现了一棵神奇的花树，假设 $1$ 为这棵树的根节点，并且在这棵树上一共有 $n$ 个节点，每个节点上都有一朵美丽的花，我们定义第 $i$ 朵花的美丽值为 $a_i$，接下来将会经过 $m$ 天，每一天可能会发生下面两种事件中的一种： - 给出三个整数 $1\,u\,w$ 表示把第 $u$ 朵花的美丽值变为 $w$。 - 给出两个整数 $2\,u$ 表示询问以 $u$ 为根节点的子树中美丽值最大的节点的值。 小明想在母亲节那天为妈妈摘下整棵树中最美丽的花朵作为礼物，因此他需要每天准确掌握这棵树的每个事件，请你帮助他设计一个程序来完成吧。 ## Input 第一行输入两个整数 $n, m$ ，分别代表节点个数和将会经过的天数。 接下来的一行有 $n$ 个整数，第 $i$ 个整数 $a_i$ 代表这朵花的美丽值。 接下来的 $n-1$ 行每行有两个整数 $u$ 和 $v$ 表示节点 $u$ 和 $v$ 之间有一条边。 接下来的 $m$ 行将会保证以下格式： - 一行中给出三个整数 $1\,u\,w$。 - 一行中给出两个整数 $2\,u$。 ## Output 对于每一种事件 $2$，每行给出一个整数代表答案。 [samples] ## Background 题目来源：2025 年广西中小学生程序设计挑战赛复赛（进阶组[试题](https://mp.weixin.qq.com/s?__biz=MzI3NDM3MzcwNQ==&mid=2247490166&idx=5&sn=e7ba7e3bc8126027b9abd662518c208b&chksm=ea9c06dd4d18206ed9d88124cc78b947298df2555889e98620204c2ea1471f58c135c00f99fb&mpshare=1&scene=23&srcid=0724dNJdhMxpUHag1dqkhiqL&sharer_shareinfo=7e47197d6e5c044ae705613db988029c&sharer_shareinfo_first=7e47197d6e5c044ae705613db988029c#rd)）。 ## Note #### 样例解释 对于样例 1，第一天以 2 为根节点的子树中美丽值最大的节点是 6，它的美丽值是 6。 第二天以 3 为根节点的子树只有它自己一个节点，所以最大美丽值节点就是它自己，值为 3。 接下来第三天将节点 3 的值变为 7。 第四天以 1 为根节点的子树就是这棵树本身，同时美丽值最大的节点为 3，它的美丽值为 7。 最后第五天以 2 为根节点的子树中美丽值最大的节点是 6，它的美丽值是 6。 #### 数据范围 - 对于 30% 的数据，保证 $1 \le n,m \le 5 \times 10^3$。 - 对于另外存在 20% 的数据保证只有事件 $2$。 - 对于 100% 的数据，保证 $1 \le n,m \le 2 \times 10^5, \;1 \le a_i, w \le 1 \times 10^9$。