← 返回题目列表

AtCoder · awc0106_c

C. 网络通信成本

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

分数: 366 分

问题陈述

有一个网络,包括 N 中继站。中继站编号为 1 to N,并且网络具有树形结构。具体来说,有 N - 1 链接,以及 j-th (1 \leq j \leq N-1) 链路双向连接中继站 U_j 和中继站 V_j.

各中继站 i 已安装天线,并带有底座坐标 (X_i, Y_i).

各中继站 i 具有“正常模式”或“反转模式”的操作模式,并且最初所有中继站都处于正常模式。

的 有效坐标 中继站的 中继站的 i的天线定义如下:

  • 普通模式下:有效坐标为 (X_i, Y_i)
  • 倒置模式下:有效坐标为 (-X_i, -Y_i)

的 通讯费用 连接相邻中继站的链路的 连接相邻中继站的链路 u 和 v 定义为其各自有效坐标之间的曼哈顿距离。即如果中继站的有效坐标 u 是 (X'_u, Y'_u) 及中继站有效坐标 v 是 (X'_v, Y'_v),通信成本为 |X'_u - X'_v| + |Y'_u - Y'_v|.

此外,还有一个整数值校正参数 S,初始值为 0.

高桥表演 Q 操作按顺序进行。有 3 操作类型:

  • 1 C : 切换中继站的操作模式 C (从正常模式切换到倒置模式,或从倒置模式切换到正常模式)。
  • 2 W :添加 W to S.
  • 3 A B :对于来自中继站的唯一简单路径 A 至中继站 B 在树上,使用每个中继站的当前操作模式和当前值计算并输出以下值 S:

\text{(sum of communication costs of each link on the path)} + S \times \text{(number of relay stations on the path)}

这里,路径上中继站的数量包括端点 A 和 B。特别是,当 A = B,有 0 链接和 1 路径上的中继站。

请注意,输出值可能为负。

约束

  • 2 \leq N \leq 5000
  • 1 \leq Q \leq 5000
  • -10^5 \leq X_i \leq 10^5
  • -10^5 \leq Y_i \leq 10^5
  • 1 \leq U_j \leq N
  • 1 \leq V_j \leq N
  • U_j \neq V_j
  • 给定的图是一棵树(连接并且没有循环)
  • 对于类型 1 操作, 1 \leq C \leq N
  • 对于类型 2 操作, -10^5 \leq W \leq 10^5
  • 对于类型 3 操作, 1 \leq A \leq N, 1 \leq B \leq N (案例 A = B 是可能的)
  • 至少有 1 类型 3 操作
  • 所有输入值均为整数

输入

N Q
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}
query_1
query_2
\vdots
query_Q
  • 第一行包含中继站数量 N 和操作次数 Q,用空格分隔。
  • 如下 N 行, i第行 (1 \leq i \leq N) 包含基础坐标 X_i, Y_i 中继站的 i,用空格分隔。
  • 如下 N - 1 行, j第行 (1 \leq j \leq N-1) 包含数字 由连接的两个中继站的 U_j, V_j 由两个中继站连接的 j第一个链接,以空格分隔。
  • 如下 Q 行, k第行 (1 \leq k \leq Q) 包含 k第次操作。每个操作均以以下格式给出:
  • 类型 1 操作: 1 C
  • 类型 2 操作: 2 W
  • 类型 3 操作: 3 A B

输出

对于每种类型 3 运算,按照运算执行的顺序在一行上输出答案。


示例输入 1

3 7
0 0
2 1
-1 3
1 2
2 3
3 1 3
1 2
3 1 3
2 5
3 2 2
1 1
3 1 2

示例输出 1

8
8
5
13

示例输入 2

4 8
1 1
-2 0
0 -3
4 -1
1 2
1 3
3 4
3 2 4
2 -2
3 1 1
1 3
3 2 4
1 4
2 7
3 4 1

示例输出 2

15
-2
7
24

示例输入 3

10 18
0 0
4 1
-3 5
7 -2
-6 -4
2 8
10 3
-8 6
1 -7
-5 9
1 2
1 3
2 4
2 5
3 6
6 7
6 8
5 9
5 10
3 4 7
1 5
3 9 10
2 3
3 4 8
1 6
3 7 8
2 -10
3 1 10
1 5
1 1
3 4 7
2 100
3 2 2
1 10
3 9 3
2 -93
3 8 10

示例输出 3

40
32
57
52
-2
14
93
503
78

示例输入 4

25 35
0 0
5 -3
-4 7
12 1
-8 -6
3 14
-15 2
20 -10
-11 9
6 6
-2 -13
17 4
-19 -8
9 -16
0 21
-7 18
13 -5
-23 3
25 12
-5 -22
8 24
-14 -17
30 -1
-28 15
2 -30
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
9 17
10 18
11 19
12 20
13 21
14 22
15 23
16 24
17 25
3 24 25
1 8
3 16 9
2 50
3 1 23
1 3
1 21
3 21 22
2 -75
3 24 20
1 1
3 1 1
1 15
2 10
3 23 25
1 8
3 16 24
1 24
3 24 25
2 -100
3 18 19
1 5
1 10
3 18 25
2 200
3 12 22
1 22
3 22 21
1 3
2 -85
3 6 6
1 1
3 2 21
1 25
3 25 24

示例输出 4

203
93
363
537
-40
-25
101
-6
142
-452
-740
650
796
0
104
261

示例输入 5

2 10
100000 -100000
-100000 100000
1 2
3 1 2
3 1 1
2 -100000
3 2 2
1 1
3 1 2
1 2
3 1 2
2 100000
3 2 1

示例输出 5

400000
0
-100000
-200000
200000
400000