問題一覧 > 通常問題

No.772 Dynamic Distance Sum

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 13
作問者 : maroon_kurimaroon_kuri / テスター : yosupotyosupot
3 ProblemId : 2587 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-12-19 23:31:00

問題文

$N$ 頂点の森があります。 頂点には $1$ から $N$ までの番号がついています。 最初、辺は $1$ つもありません。
また、各頂点 $v$ には整数 $X_v$ が定められています。 最初、すべての $v$ について $X_v=1$ です。
クエリが $Q$ 個与えられます。 各クエリは、以下の $3$ 種類のいずれかです。

  • タイプ $1$： $2$ 頂点 $a,b$ 、整数 $c$ が指定される。頂点 $a$ と頂点 $b$ の間に、重み $c$ の辺を張る。辺を張ったあとでもグラフが森であることは保証される。
  • タイプ $2$： $2$ 頂点 $a,b$ が指定される。頂点 $a$ と頂点 $b$ の間を直接結ぶ辺を削除する。そのような辺が存在することは保証される。
  • タイプ $3$： 頂点 $a$ が指定される。まず、$X_a$ の値を $1-X_a$ で置き換える。その後、頂点 $a$ が属する木について、次の問題を解く。
    木の頂点を $v_1,v_2,...v_k$ とする。 $\min_{1 \leq i \leq k}\{\sum_{1 \leq j \leq k} dist(v_i,v_j) \times X_{v_j}\}$ を求める。 なお、$dist(v_i,v_j)$ は、頂点 $v_i,v_j$ 間のパスに含まれる辺の重みの総和である。
これらのクエリをオンラインで処理するプログラムを書いてください。

入力

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

$1 \leq N \leq 10^5$
$1 \leq Q \leq 3 \times 10^5$
各タイプごとのクエリの書式、及び制約は以下の通りである。

  • タイプ $1$：　$1\ a\ b\ c$　($1 \leq a,b \leq N$, $a \neq b$, $1 \leq c \leq 10^8$)
  • タイプ $2$：　$2\ a\ b$　($1 \leq a,b \leq N$, $a \neq b$)
  • タイプ $3$：　$3\ a$　($1 \leq a \leq N$)

なお、それぞれのクエリにおいて指定される頂点番号（クエリタイプ $1,2$ における $a,b$、クエリタイプ $3$ における $a$）は暗号化されているため、復号化する必要がある。 具体的には、入力で与えられた頂点番号が $x$、今までのタイプ $3$ クエリの答えの総和が $S$ である時、暗号化前の頂点番号は、$(x-1+S) \bmod n+1$ と復号化される。

出力

タイプ $3$ のクエリに対する回答を $1$ 行ずつ出力してください。
最後に改行してください。

サンプル

サンプル1
入力
3 7
1 1 2 3
1 3 1 1
3 1
2 1 3
3 1
1 2 1 2
3 2
出力
4
0
0

$1$ つめのタイプ $3$ のクエリが与えられた時点を考えます。 頂点 $1,2$ 間に重さ $3$ の辺、頂点 $1,3$ 間に重さ $1$ の辺が張ってあります。 $X_1$ の値が $1$ から $0$ へ変化し、$X_1=0,\ X_2=1,\ X_3=1$ となります。 $dist(1,1) \times X_1 + dist(1,2) \times X_2 + dist(1,3) \times X_3 =4$ であり、これが最小です。
次にタイプ $2$ のクエリが与えられますが、消すべき辺は $((1-1+4) \bmod 3+1,(3-1+4) \bmod 3+1)=(2,1)$ です。
$2$ つめのタイプ $3$ のクエリが与えられた時点を考えます。 $X_2$ の値が $1$ から $0$ へ変化し、$X_1=0,\ X_2=0,\ X_3=1$ となります。 頂点 $2$ が属する木は、頂点 $2$ のみからなる木であり、答えは $0$ です。
$3$ つめのタイプ $3$ のクエリが与えられた時点を考えます。 頂点 $1,3$ 間に重さ $1$ の辺、頂点 $2,3$ 間に重さ $2$ の辺が張ってあります。 $X_3$ の値が $1$ から $0$ へ変化し、$X_1=0,\ X_2=0,\ X_3=0$ となります。 $dist(1,1) \times X_1 + dist(1,2) \times X_2 + dist(1,3) \times X_3 =0$ であり、これが最小です。

サンプル2
入力
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
出力
18
2
0
0
9

サンプル3
入力
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
出力
274612258
215521477
187109093
171839251
211638922
68332023
151324465
224010174
0
223740409

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