分数: 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