← 返回题目列表

Codeforces · 1575/I

I. 沙漠的幻象

中文机器翻译题面 查看原题

查内克·琼斯回来了,帮助他失散多年的亲戚印第安纳·琼斯在埋藏在充满幻想的沙漠下的迷宫中找到秘密宝藏。

迷宫的地图形成一棵树,其中有 $$$n$$$ 个房间,编号从 $$$1$$$ 到 $$$n$$$ 以及连接它们的 $$$n - 1$$$ 隧道,这样就可以通过几条隧道在每对房间之间移动。

第 $$$i$$$ 个房间 ($$$1 \leq i \leq n$$$) 的错觉率为 $$$a_i$$$。要从第$$$x$$$个房间到第$$$y$$$个房间,$$$x$$$和$$$y$$$之间必须存在一条隧道,并且需要$$$\max(|a_x + a_y|, |a_x - a_y|)$$$能量。 $$$|z|$$$ 表示$$$z$$$ 的绝对值。

为了防止盗墓,迷宫可以改变其中任意房间的幻象率。查内克和印第安纳会提出 $$$q$$$ 问题。

有两种类型的查询需要完成:

- $$$1\ u\ c$$$ — 第 $$$x$$$ 个房间的幻觉率更改为 $$$c$$$ ($$$1 \leq u \leq n$$$, $$$0 \leq |c| \leq 10^9$$$)。
- $$$2\ u\ v$$$ — Chanek 和 Indiana 询问你如果他们最初在 $$$u$$$ 房间($$$1 \leq u, v \leq n$$$),则在 $$$v$$$ 房间拿走秘密宝藏所需的最低能量。

帮助他们,这样你就可以获得宝藏的一部分!

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq q \leq 10^5$$$) — 迷宫中的房间数和查询数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq |a_i| \leq 10^9$$$) — 每个房间的初始错觉率。

接下来的 $$$n-1$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$s_i$$$ 和 $$$t_i$$$ ($$$1 \leq s_i, t_i \leq n$$$),这意味着有一条隧道连接第 $$$s_i$$$ 个房间和第 $$$t_i$$$ 个房间。给定的边形成一棵树。

接下来的 $$$q$$$ 行包含所描述的查询。给定的查询有效。

输出

对于每种类型的$$$2$$$查询,输出一行包含一个整数——查内克和印第安纳获取秘密宝藏所需的最小能量总和。

示例

输入 #1

6 4
10 -9 2 -1 4 -6
1 5
5 4
5 6
6 2
6 3
2 1 2
1 1 -3
2 1 2
2 3 3

输出 #1

39
32
0

注意

在第一个查询中,他们从 $$$1$$$-st 房间移动到 $$$2$$$-nd 房间如下。

- $$$1 \rightarrow 5$$$ — 需要 $$$\max(|10 + 4|, |10 - 4|) = 14$$$ 能量。
- $$$5 \rightarrow 6$$$ — 需要 $$$\max(|4 + (-6)|, |4 - (-6)|) = 10$$$ 能量。
- $$$6 \rightarrow 2$$$ — 需要 $$$\max(|-6 + (-9)|, |-6 - (-9)|) = 15$$$ 能量。

在第二个查询中,$$$1$$$-st 房间的幻觉率从 $$$10$$$ 变为 $$$-3$$$。

在第三个查询中,他们从$$$1$$$-st 到$$$2$$$-nd 房间的移动如下。

- $$$1 \rightarrow 5$$$ — 需要 $$$\max(|-3 + 4|, |-3 - 4|) = 7$$$ 能量。
- $$$5 \rightarrow 6$$$ — 需要 $$$\max(|4 + (-6)|, |4 - (-6)|) = 10$$$ 能量。
- $$$6 \rightarrow 2$$$ — 需要 $$$\max(|-6 + (-9)|, |-6 - (-9)|) = 15$$$ 能量。

现在,需要 $$$32$$$ 能量。