No.772 Dynamic Distance Sum
タグ : / 解いたユーザー数 19
作問者 :
maroon_kuri
/ テスター :
yosupot
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$.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。