No.772 Dynamic Distance Sum
タグ : / 解いたユーザー数 15
作問者 :


問題文
また、各頂点
クエリが
- タイプ
: 頂点 、整数 が指定される。頂点 と頂点 の間に、重み の辺を張る。辺を張ったあとでもグラフが森であることは保証される。 - タイプ
: 頂点 が指定される。頂点 と頂点 の間を直接結ぶ辺を削除する。そのような辺が存在することは保証される。 - タイプ
: 頂点 が指定される。まず、 の値を で置き換える。その後、頂点 が属する木について、次の問題を解く。
木の頂点を とする。 を求める。 なお、 は、頂点 間のパスに含まれる辺の重みの総和である。
入力
各タイプごとのクエリの書式、及び制約は以下の通りである。
- タイプ
: ( , , ) - タイプ
: ( , ) - タイプ
: ( )
なお、それぞれのクエリにおいて指定される頂点番号(クエリタイプ
出力
タイプ
最後に改行してください。
サンプル
サンプル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
次にタイプ
サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。