C - ネットワークの通信コスト 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

N 個の中継局からなるネットワークがあります。中継局には 1 から N までの番号が付いており、ネットワークは木構造をしています。具体的には、N - 1 本の回線があり、j 番目 (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 : S に W を加算する。
  • 3 A B : 中継局 A から中継局 B までの木上の唯一の単純パスについて、その時点での各中継局の動作モードおよび S の値を用いて以下の値を計算し、出力する。

\text{(パス上の各回線の通信コストの総和)} + S \times \text{(パス上の中継局の個数)}

ここで、パス上の中継局の個数は端点 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 の場合もある）
  • 種類 3 の操作は 1 個以上存在する
  • 入力はすべて整数

入力

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
  • 1 行目には、中継局の数 N と操作の数 Q がスペース区切りで与えられる。
  • 続く N 行のうち i 行目 (1 \leq i \leq N) には、中継局 i の基準座標 X_i, Y_i がスペース区切りで与えられる。
  • 続く N - 1 行のうち j 行目 (1 \leq j \leq N-1) には、j 番目の回線が結ぶ 2 つの中継局の番号 U_j, V_j がスペース区切りで与えられる。
  • 続く Q 行のうち k 行目 (1 \leq k \leq Q) には、k 番目の操作が与えられる。各操作は以下の形式で与えられる。
  • 種類 1 の操作: 1 C
  • 種類 2 の操作: 2 W
  • 種類 3 の操作: 3 A B

出力

種類 3 の操作それぞれについて、答えを 1 行に 1 つずつ、操作が行われた順に出力せよ。

入力例 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

Score : 366 pts

Problem Statement

There is a network consisting of N relay stations. The relay stations are numbered from 1 to N, and the network has a tree structure. Specifically, there are N - 1 links, and the j-th (1 \leq j \leq N-1) link bidirectionally connects relay station U_j and relay station V_j.

Each relay station i has an antenna installed, with base coordinates (X_i, Y_i).

Each relay station i has an operation mode of either "normal mode" or "inverted mode", and initially all relay stations are in normal mode.

The effective coordinates of relay station i's antenna are defined as follows:

  • In normal mode: the effective coordinates are (X_i, Y_i)
  • In inverted mode: the effective coordinates are (-X_i, -Y_i)

The communication cost of a link connecting adjacent relay stations u and v is defined as the Manhattan distance between their respective effective coordinates. That is, if the effective coordinates of relay station u are (X'_u, Y'_u) and the effective coordinates of relay station v are (X'_v, Y'_v), the communication cost is |X'_u - X'_v| + |Y'_u - Y'_v|.

Additionally, there is an integer-valued correction parameter S, with an initial value of 0.

Takahashi performs Q operations in order. There are 3 types of operations:

  • 1 C : Toggle the operation mode of relay station C (switch from normal mode to inverted mode, or from inverted mode to normal mode).
  • 2 W : Add W to S.
  • 3 A B : For the unique simple path from relay station A to relay station B on the tree, compute and output the following value using the current operation modes of each relay station and the current value of S:

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

Here, the number of relay stations on the path includes the endpoints A and B. In particular, when A = B, there are 0 links and 1 relay station on the path.

Note that the output value may be negative.

Constraints

  • 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
  • The given graph is a tree (connected and has no cycles)
  • For type 1 operations, 1 \leq C \leq N
  • For type 2 operations, -10^5 \leq W \leq 10^5
  • For type 3 operations, 1 \leq A \leq N, 1 \leq B \leq N (the case A = B is possible)
  • There is at least 1 type 3 operation
  • All input values are integers

Input

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
  • The first line contains the number of relay stations N and the number of operations Q, separated by a space.
  • In the following N lines, the i-th line (1 \leq i \leq N) contains the base coordinates X_i, Y_i of relay station i, separated by a space.
  • In the following N - 1 lines, the j-th line (1 \leq j \leq N-1) contains the numbers U_j, V_j of the two relay stations connected by the j-th link, separated by a space.
  • In the following Q lines, the k-th line (1 \leq k \leq Q) contains the k-th operation. Each operation is given in the following format:
  • Type 1 operation: 1 C
  • Type 2 operation: 2 W
  • Type 3 operation: 3 A B

Output

For each type 3 operation, output the answer on a single line, in the order the operations are performed.

Sample Input 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

Sample Output 1

8
8
5
13

Sample Input 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

Sample Output 2

15
-2
7
24

Sample Input 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

Sample Output 3

40
32
57
52
-2
14
93
503
78

Sample Input 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

Sample Output 4

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

Sample Input 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

Sample Output 5

400000
0
-100000
-200000
200000
400000