問題一覧 > 通常問題

No.772 Dynamic Distance Sum

レベル : / AI推定難易度 : 3200 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 19
作問者 : maroon_kuri / テスター : yosupot
お気に入りにしたユーザー ProblemId : 2587 / 自分の提出
問題文最終更新日: 2018-12-19 23:31:00
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2018 (順位表) の他の問題:

Problem Statement

There is a forest with $N$ vertices. The vertices are numbered from $1$ to $N$. Initially, there is not even $1$ edge.
Also, an integer $X_v$ is defined for each vertex $v$. Initially, $X_v=1$ for all $v$.
You are given $Q$ queries. Each query is one of the following $3$ types.

  • Type $1$: $2$ vertices $a,b$ and an integer $c$ are specified. Add an edge of weight $c$ between vertex $a$ and vertex $b$. It is guaranteed that the graph remains a forest after adding the edge.
  • Type $2$: $2$ vertices $a,b$ are specified. Delete the edge directly connecting vertex $a$ and vertex $b$. It is guaranteed that such an edge exists.
  • Type $3$: A vertex $a$ is specified. First, replace the value of $X_a$ with $1-X_a$. Then, solve the following problem for the tree containing vertex $a$.
    Let $v_1,v_2,...v_k$ be the vertices of the tree. Find $\min_{1 \leq i \leq k}\{\sum_{1 \leq j \leq k} dist(v_i,v_j) \times X_{v_j}\}$. Here, $dist(v_i,v_j)$ is the sum of the weights of the edges on the path between vertices $v_i,v_j$.
Write a program that processes these queries online.

Input

$N\ Q$
$Query_1$
$Query_2$
$:$
$Query_Q$

$1 \leq N \leq 10^5$
$1 \leq Q \leq 3 \times 10^5$
The format and constraints of each query type are as follows.

  • Type $1$: $1\ a\ b\ c$ ($1 \leq a,b \leq N$, $a \neq b$, $1 \leq c \leq 10^8$)
  • Type $2$: $2\ a\ b$ ($1 \leq a,b \leq N$, $a \neq b$)
  • Type $3$: $3\ a$ ($1 \leq a \leq N$)

Note that the vertex numbers specified in each query ($a,b$ in query types $1,2$, and $a$ in query type $3$) are encrypted and must be decrypted. Specifically, when the vertex number given in the input is $x$ and the sum of the answers to all type $3$ queries so far is $S$, the vertex number before encryption is obtained by decrypting it as $(x-1+S) \bmod n+1$.

Output

For the type $3$ queries, output the answers, $1$ per line.
Print a newline at the end.

Sample

Sample 1
Input
3 7
1 1 2 3
1 3 1 1
3 1
2 1 3
3 1
1 2 1 2
3 2
Output
4
0
0

Consider the moment when the $1$st query of type $3$ is given. There is an edge of weight $3$ between vertices $1,2$ and an edge of weight $1$ between vertices $1,3$. The value of $X_1$ changes from $1$ to $0$, resulting in $X_1=0,\ X_2=1,\ X_3=1$. We have $dist(1,1) \times X_1 + dist(1,2) \times X_2 + dist(1,3) \times X_3 =4$, and this is the minimum.
Next, a query of type $2$ is given, and the edge to delete is $((1-1+4) \bmod 3+1,(3-1+4) \bmod 3+1)=(2,1)$.
Consider the moment when the $2$nd query of type $3$ is given. The value of $X_2$ changes from $1$ to $0$, resulting in $X_1=0,\ X_2=0,\ X_3=1$. The tree containing vertex $2$ consists of only vertex $2$, so the answer is $0$.
Consider the moment when the $3$rd query of type $3$ is given. There is an edge of weight $1$ between vertices $1,3$ and an edge of weight $2$ between vertices $2,3$. The value of $X_3$ changes from $1$ to $0$, resulting in $X_1=0,\ X_2=0,\ X_3=0$. We have $dist(1,1) \times X_1 + dist(1,2) \times X_2 + dist(1,3) \times X_3 =0$, and this is the minimum.

Sample 2
Input
5 17
1 1 5 10
1 3 1 7
1 5 2 5
1 3 4 2
2 3 1
1 4 1 6
2 5 2
3 1
3 2
3 2
1 2 1 2
3 4
2 5 1
1 4 5 2
2 3 4
1 3 5 9
3 5
Output
18
2
0
0
9

Sample 3
Input
10 37
1 2 3 6428496
1 7 10 41603701
1 2 7 61903527
1 1 6 57606292
1 2 1 43682226
1 8 2 59090781
3 6
3 10
1 10 7 15269842
3 6
3 7
1 3 10 39799671
1 3 5 28501778
3 5
2 1 10
1 6 10 37641690
2 9 6
3 8
1 6 8 89420938
3 9
2 6 3
1 9 6 17757145
2 9 3
1 1 9 26575112
2 3 8
1 2 1 19670627
2 3 5
1 1 5 12760556
2 3 4
1 4 1 36949637
3 7
2 6 9
1 6 8 74850387
2 3 8
3 3
1 7 3 77007154
3 3
Output
274612258
215521477
187109093
171839251
211638922
68332023
151324465
224010174
0
223740409

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。