倉庫 \(k\) にある荷物の重さの合計を配列 \(v\) を用いて管理することを考えます。

この問題で行われる操作は以下の \(2\) 通りです。操作を配列に対する演算に言い換えると以下の通りになります。

• 倉庫 \(a\) にある荷物を全て倉庫 \(b\) に移動させる
  • まず、 \(v[b]\) に \(v[a]\) を加算します。
  • 次に、 \(v[a]\) を \(0\) にする。
• 倉庫 \(c\) にある荷物の重さの合計を答える
  • 単に \(v[c]\) を答えればよいです。

時間計算量は \(O(N+Q)\) 、空間計算量は \(O(N)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ll n,q;
  cin >> n >> q;
  vector<ll> v(n+1);
  for(ll i=1;i<=n;i++){ cin >> v[i]; }
  while(q--){
    ll typ;
    cin >> typ;
    if(typ==1){
      ll a,b;
      cin >> a >> b;
      v[b]+=v[a];
      v[a]=0;
    }
    else{
      ll c;
      cin >> c;
      cout << v[c] << "\n";
    }
  }
  return 0;
}