問題一覧 > 通常問題

No.3025 Chocol∀te

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 38
作問者 : 👑 potato167 / テスター : noya2
0 ProblemId : 11931 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-02-14 15:31:38

ストーリー(読まなくていい)

ここだけの話、となりのクラスでは友チョコを配り合う文化がありました。 ある人は自分の友達全員に同じ数のチョコレートを配ります。

腐れ外道のあなたはバレンタイン当日にクラスの人を 11 人選び、チョコレートを全て盗むことにしました。

しかし、バレンタイン前日に魔法少女がクラスに魔法をかけ、友達関係や配るチョコの数を変える計画があることを知りました。 魔法少女は魔法をかけることを正直もうやめたいと思っているので、いつ魔法をやめるかわかりませんでした。

あなたは、魔法少女があるタイミングで魔法をやめたときに、狙った人のチョコレートを盗むと何個のチョコレートを実際に盗めるのかが知りたくなりました。

そこで、友達関係をグラフに置き換えた以下の問題を解くことにしました。

問題文

NN 頂点 MM 辺の単純無向グラフが与えられます。頂点には 1,2,,N1, 2, \dots , N の番号が付けられています。はじめ、ii 番目の辺は頂点 xix_{i} と頂点 yiy_{i} を結んでいます。また、長さ NN の正整数列 A=(A1,A2,,AN)A = (A_{1}, A_{2}, \dots , A_{N}) も与えられます。 QQ 個のクエリが与えられるので、与えられた順に処理してください。各クエリは以下の 33 種類です。

  • 1 u v : 頂点 uuvv の間に辺が存在するならその辺を削除し、そうでないなら頂点 uuvv の間に辺を追加する。
  • 2 p a : AApp 番目の要素を aa に変更する。
  • 3 c : 集合 SS を頂点 cc と隣接している頂点の番号の集合とする。このとき、iSAi\displaystyle \sum_{i\in S} A_{i} を出力する。

制約

  • 2N1052\leq N\leq 10^{5}
  • 1Mmin(105,N(N1)2)1\leq M \leq \min(10^{5}, \frac{N(N - 1)}{2})
  • 1xi<yiN1\leq x_{i} < y_{i} \leq N
  • ij(xi,yi)(xj,yj)i \neq j \to (x_{i}, y_{i}) \neq (x_{j}, y_{j})
  • 1Ai1091\leq A_{i} \leq 10^{9}
  • 1Q1051\leq Q\leq 10^{5}
  • 1u<vN1\leq u < v \leq N
  • 1pN1\leq p \leq N
  • 1a1091\leq a \leq 10^{9}
  • 1cN1\leq c\leq N
  • 入力は全て整数
  • 出力クエリが少なくとも 11 つある

入力

入力は以下の形式で標準入力から与えられます。

NN MM
x1x_{1} y1y_{1}
x2x_{2} y2y_{2}
\vdots
xMx_{M} yMy_{M}
A1A_{1} A2A_{2} \dots ANA_{N}
QQ
query1\text{query}_{1}
query2\text{query}_{2}
\vdots
queryQ\text{query}_{Q}

各クエリ queryi\text{query}_{i} は以下のいずれかの形式で与えられます。

11 uu vv
22 pp aa
33 cc

出力

問題文の指示に従って、クエリへの答えを改行区切りで出力してください。

サンプル

サンプル1
入力
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
出力
10010
1100
20010
120000
21900

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