問題一覧 > 通常問題

No.3025 Chocol∀te

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 40
作問者 : 👑 potato167 / テスター : noya2
お気に入りにしたユーザー ProblemId : 11931 / 自分の提出
問題文最終更新日: 2025-02-14 15:31:38
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
yukicoder contest 456 オムニバス (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。