No.3025 Chocol∀te
Story (you don't have to read this)
Just between us, the class next door had a custom of handing out friendship chocolates to one another. Each person gives the same number of chocolates to every one of their friends.
Being an utter scoundrel, you decided to choose $1$ person in the class on Valentine's Day and steal all of their chocolates.
However, on the day before Valentine's Day, you learned that a magical girl plans to cast magic on the class, changing friendships and the number of chocolates handed out. The magical girl honestly wants to stop casting magic already, so there was no telling when she would stop.
You became curious how many chocolates you could actually steal from your target if the magical girl stopped casting magic at a given moment.
So you decided to solve the following problem, in which friendships are represented as a graph.
Problem Statement
You are given a simple undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1, 2, \dots , N$. Initially, the $i$-th edge connects vertices $x_{i}$ and $y_{i}$. You are also given a sequence of positive integers $A = (A_{1}, A_{2}, \dots , A_{N})$ of length $N$. $Q$ queries are given; process them in the given order. Each query is one of the following $3$ types.
1 u v: If an edge exists between vertices $u$ and $v$, delete that edge; otherwise, add an edge between vertices $u$ and $v$.2 p a: Change the $p$-th element of $A$ to $a$.3 c: Let $S$ be the set of the numbers of the vertices adjacent to vertex $c$. Output $\displaystyle \sum_{i\in S} A_{i}$.
Constraints
- $2\leq N\leq 10^{5}$
- $1\leq M \leq \min(10^{5}, \frac{N(N - 1)}{2})$
- $1\leq x_{i} < y_{i} \leq N$
- $i \neq j \to (x_{i}, y_{i}) \neq (x_{j}, y_{j})$
- $1\leq A_{i} \leq 10^{9}$
- $1\leq Q\leq 10^{5}$
- $1\leq u < v \leq N$
- $1\leq p \leq N$
- $1\leq a \leq 10^{9}$
- $1\leq c\leq N$
- All input values are integers.
- There is at least $1$ output query.
Input
The input is given from standard input in the following format.
$N$ $M$
$x_{1}$ $y_{1}$
$x_{2}$ $y_{2}$
$\vdots$
$x_{M}$ $y_{M}$
$A_{1}$ $A_{2}$ $\dots$ $A_{N}$
$Q$
$\text{query}_{1}$
$\text{query}_{2}$
$\vdots$
$\text{query}_{Q}$
Each query $\text{query}_{i}$ is given in one of the following formats.
$1$ $u$ $v$
$2$ $p$ $a$
$3$ $c$
Output
Following the instructions in the problem statement, output the answers to the queries, separated by newlines.
Sample
Sample 1
Input
6 6 1 2 1 3 1 4 2 4 3 4 5 6 10 100 1000 10000 100000 1000000 10 3 3 2 4 20000 1 1 4 1 4 6 3 1 3 3 3 6 1 1 4 2 2 900 3 1
Output
10010 1100 20010 120000 21900
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2