algorithm.cpp

#include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp>
using namespace std;
// using namespace boost::multiprecision;

# define REP(i,n) for (int i=0;i<(n);++i)
# define rep(i,a,b) for(int i=a;i<(b);++i)
# define all(v) v.begin(),v.end()
# define showVector(v) REP(i,v.size()){cout << (v[i]) << " ";} cout << endl;
template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;}
typedef long long int ll;
typedef pair<ll,ll> P_ii;
typedef pair<double,double> P_dd;

template<class T>
using MaxHeap = std::priority_queue<T>;

template<class T>
using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
  return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}



template<typename T>
T gcd(T a, T b) {
  if(a < b) swap(a,b);
    
  if(b == 0) return a;
  return gcd(b, a % b);
}

ll lcm(ll a, ll b){
  ll g = gcd(a,b);
  return (a/g)*b;
}

// 素数判定 O(√n)
bool is_prime(ll n){
  if(n == 1) return false;
  for(ll i = 2; i * i <= n; i++){
    if(n % i == 0) return false;
  }
  return true;
}

// 約数列挙 O(√n)
vector<ll> divisor(ll n){
  vector<ll> res;
  for(ll i = 1; i * i <= n; i++){
    if(n % i == 0){
      res.push_back(i);
      if(i != n / i) res.push_back(n / i);
    }
  }
  return res;
}

template<typename T>

// エラトステネスの篩
// return lp[i] := iの最小素因数(lp[i] == iならば素数)
vector<int> SieveOfEratosthenes(int N = 10000000){
  vector<int> lp(N + 1, 0);
  vector<int> pr;
  for (int i=2; i<=N; ++i) {
    if (lp[i] == 0) {
      lp[i] = i;
      pr.push_back(i);
    }
    for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
      lp[i * pr[j]] = pr[j];
  }
  return lp;
}

// modint
const ll mod = 1e9+7;
template< int mod >
struct ModInt {
  int x;
  ModInt() : x(0) {}
  ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
  ModInt &operator+=(const ModInt &p) {
    if((x += p.x) >= mod) x -= mod;
    return *this;
  }
  ModInt &operator-=(const ModInt &p) {
    if((x += mod - p.x) >= mod) x -= mod;
    return *this;
  }
  ModInt &operator*=(const ModInt &p) {
    x = (int) (1LL * x * p.x % mod);
      return *this;
  }
  ModInt &operator/=(const ModInt &p) {
    *this *= p.inv();
    return *this;
  }
  ModInt operator-() const { return ModInt(-x); }
  ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
  ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
  ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
  ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
  bool operator==(const ModInt &p) const { return x == p.x; }
  bool operator!=(const ModInt &p) const { return x != p.x; }
    
  ModInt inv() const {
    int a = x, b = mod, u = 1, v = 0, t;
    while(b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }
  
  ModInt pow(int64_t n) const {
    ModInt ret(1), mul(x);
    while(n > 0) {
      if(n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }
  
  friend ostream &operator<<(ostream &os, const ModInt &p) {
    return os << p.x;
  }
  
  friend istream &operator>>(istream &is, ModInt &a) {
    int64_t t;
    is >> t;
    a = ModInt< mod >(t);
    return (is);
  }
  
  static int get_mod() { return mod; }
};
 
using mint = ModInt<mod>;

ll mypow(ll x, ll n){
  if(n == 0)
    return 1;
 
  if(n % 2 == 0)
    return mypow(x * x, n / 2);
  else
    return x * mypow(x, n - 1);
}
 

// 素因数分解
long long MOD = 1000000000 + 7;

template<typename T>
map<T, ll> prime_factorize(T x){
  map<T, ll> res;

  while(x%2==0){
    x/=2;
    res[2]++;
  }

  for(ll i=3;i*i<=x;i+=2){
    while(x%i==0){
      x/=i;
      res[i]++;
    }
  }
  if(x!=1) res[x]++;
  return res;
}



// ランレングス圧縮
vector<pair<char,int>> run_comp(string S){
  vector<pair<char,int>> v;
  char now = S[0];
  int num = 1;
  char tmp = S[S.size()-1];
  for(int i = 1; i < S.size(); i++){
    tmp = S[i];
    if(now == tmp){
      num++;
    } else { 
      v.push_back(make_pair(now, num));
      num = 1;
      now = tmp;
    }
  }
  v.push_back(make_pair(tmp, num));
  return v;
}

// union find
struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};


// nCrの計算
const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++){
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

// 二項係数計算
long long COM(int n, int k){
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
    // 前処理
    COMinit();

    // 計算例
    cout << COM(100000, 50000) << endl;
}



/* 大文字を小文字に変換 */
char tolower(char c) {
  return (c + 0x20);
}

/* 小文字を大文字に変換 */
char toupper(char c) {
  return (c - 0x20);
}


// dijkstra法 
ll INF = 10000000000000000;
vector<vector<int>> v;
vector<ll> dist;
map<pii, ll> len;
 
 
bool operator>(pil x, pil y){
  return x.second > y.second;
}
 
void shortest_path(int s){
  // sから各点への最短距離計算
  dist.assign(N,INF);
  priority_queue<pil, vector<pil>, greater<pil>> q;
 
  dist[s] = 0;
  map<int,int> check;
  q.push(make_pair(s, dist[s]));
  check[s] = 1;
 
  while(!q.empty()){
    pil now = q.top();
    int now_v = now.first;
    ll now_dist = now.second;
    check[now_v] = 1;
    q.pop();
 
    if(dist[now_v] < now_dist) continue;
    
    for(int next_v: v.at(now_v)){
      if(dist[next_v] > dist[now_v] + len[make_pair(now_v, next_v)]){
        dist[next_v] = dist[now_v] + len[make_pair(now_v, next_v)];
        q.push(make_pair(next_v, dist[next_v]));
      }
    }
  }
}


// LCS
string LCS(string s, string t){
 	int n, m;
	n = s.length();
	m = t.length();

	// dp[i][j] : sのi文字目、tのj文字目のLCSの長さ
  vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
 
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(s[i-1] == t[j-1]){
				dp[i][j] = dp[i-1][j-1] + 1;
			}else{
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
			}
		}
	}
 
	// dp配列を逆からたどってLCSを作成する
	// LCSの長さが更新されたときの文字を追加していく
 
	string ans = "";
	int x = n;
	int y = m;
	while(x > 0 && y > 0){
		if(dp[x][y] == dp[x-1][y]){
			x--;
		}else if(dp[x][y] == dp[x][y-1]){
			y--;
		}else{
			x--;
			y--;
      ans += s[x];
		}
	}
 
	reverse(ans.begin(), ans.end());
  return ans;
}


// LCA
// ダブリングと根からの距離で頑張る

vector<vector<int>> parent;
map<int,int> dist;

int query(int x, int y){
  // xとyのLCAまでの距離を求めて、
  // x->LCA->y->xという閉路の長さを返す
  if(dist[x] < dist[y]){
    return query(y,x);
  }

  int in = x;
  int out = y;

  // cerr << "before: x: " << x << " y: " << y << endl;
  if(dist[x] != dist[y]){
    int up = dist[x] - dist[y];
    int log_up = log2(up);
    // xのup個上に
    for(ll k = log_up; k >= 0; k--){
      if((up>>k)&1){
        x = parent[k][x];
      }
    }
    // cerr << "after: x: " << x << " y: " << y << endl;
  }

  int lca;
  if(x == y){
    lca = x;
  } else {
    int height = parent.size();
    for(int i = height -1; i >= 0; i--){
      if(parent[i][x] != parent[i][y]){
        x = parent[i][x];
        y = parent[i][y];
      }
    }
    // cerr << "LCA: " << parent[0][x] << endl;
    lca = parent[0][x];
  }

  return lca;
}

int main(){
  int N;
  cin >> N;
  vector<vector<int>> v(N);
  int root;
  for(int i = 0; i < N; i++){
    int tmp;
    cin >> tmp;
    if(tmp == -1){
      root = i;
    } else { 
      tmp--;
      v.at(i).push_back(tmp);
      v.at(tmp).push_back(i);
    }
  }

  // 0からの距離
  dist[root] = 0;
  queue<int> q;
  q.push(root);

  int log_N = floor(log2(N));
  // cerr << N << " " << log_K << endl;
  parent.assign(log_N+1, vector<int>(N));

  parent[0][root] = -1;

  while(!q.empty()){
    int now = q.front();
    q.pop();

    for(int next: v.at(now)){
      if(dist.count(next) == 0){
        parent[0][next] = now;
        dist[next] = dist[now] + 1;
        q.push(next);
      }
    }
  }

  // ダブリング 
  for(int k = 0; k < log_N; k++){
    for(int i = 0; i < N; i++){
      if(parent[k][i] == -1){
        parent[k+1][i] = -1;
      } else { 
        parent[k+1][i] = parent[k][parent[k][i]];
      }
    }
  }


  int Q;
  cin >> Q;
  for(int i= 0; i < Q; i++){
    int tmp1,tmp2;
    cin >> tmp1 >> tmp2;
    tmp1--;
    tmp2--;
    int lca = query(tmp1,tmp2);
    string ans;
    if(tmp2 == lca){
      ans = "Yes";
    } else {
      ans = "No";
    }
    cout << ans << endl;

  }

}


// 2次元累積和
int main() {
  // 入力: H × W のグリッド
  int H, W; cin >> H >> W;
  vector<vector<int> > a(H, vector<int>(W));
  for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) cin >> a[i][j];

  // 二次元累積和
  vector<vector<int> > s(H+1, vector<int>(W+1, 0));
  for (int i = 0; i < H; ++i)
    for (int j = 0; j < W; ++j)
      s[i+1][j+1] = s[i][j+1] + s[i+1][j] - s[i][j] + a[i][j];

  // クエリ [x1, x2) × [y1, y2) の長方形区域の和
  int Q; cin >> Q;
  for (int q = 0; q < Q; ++q) {
    int x1, x2, y1, y2;
    cin >> x1 >> x2 >> y1 >> y2;
    cout << s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1] << endl;
  }
}  

// セグメントツリー (区間和、区間最大値、区間最小値、区間最大公約数)
template<typename T>
T gcd(T a, T b) {
  if(a < b) swap(a,b);
    
  if(b == 0) return a;
  return gcd(b, a % b);
}
typedef long long ll;
int const inf = INT_MAX / 2;
 
enum query_type { min_query, max_query, sum_query, gcd_query};
 
template<class T> struct segtree {
  int N;
  vector<T> dat, sum;
  function<T(T, T)> func;
  T ngvalue;
 
  void init(int n, function<T(T, T)> const& f, T ng) {
    N = 1;
    while(N < n) N <<= 1;
    dat.assign(2 * N - 1, 0);
    sum.assign(2 * N - 1, 0);
    func = f;
    ngvalue = ng;
  }
 
  segtree() = default;
 
  segtree(int n, query_type qtype) {
    if(qtype == min_query) {
      init(n, [](T a, T b){return min(a, b);}, numeric_limits<T>::max());
    }
    else if(qtype == max_query) {
      init(n, [](T a, T b){return max(a, b);}, numeric_limits<T>::min());
    }
    else if(qtype == sum_query) {
      init(n, [](T a, T b){return a + b;}, 0);
    }
    else if(qtype == gcd_query) {
      init(n, [](T a, T b){return gcd(a,b);}, 0);
    }
    else {
      runtime_error("no matching query type");
    }
  }
 
  void add(int i, T x) {
    add(i, i + 1, x);
  }
 
  void add(int a, int b, T x) {
    add(a, b, x, 0, 0, N);
  }
 
  T add(int a, int b, T x, int k, int l, int r) {
    if(b <= l || r <= a) return dat[k];
    if(a <= l && r <= b) {
      sum[k] += x;
      return dat[k] += x;
    }
    int m = (l + r) / 2;
    return dat[k] = func(add(a, b, x, 2 * k + 1, l, m), add(a, b, x, 2 * k + 2, m, r)) + sum[k];
  }
 
  T operator()(int a, int b) {
    return query(a, b, 0, 0, N);
  }
 
  T query(int a, int b, int k, int l, int r) {
    if(b <= l || r <= a) return ngvalue;
    if(a <= l && r <= b) return dat[k];
    int m = (l + r) / 2;
    return func(query(a, b, 2 * k + 1, l, m), query(a, b, 2 * k + 2, m, r)) + sum[k];
  }
};
// segtree<int> st(N+2, sum_query);
// st(a,b)
// st.add(i,1)



// クラスカル法
typedef pair<int,int> pii;

long long MOD = 1000000000 + 7;

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

int main(){
  cout << setprecision(10);
  int N,M; cin >> N >> M;
  vector<pair<int, pair<int,int>>> v(M);

  for(int i = 0; i < M; i++){
    int x,y,z; cin >> x >> y >> z;
    v[i] = make_pair(z, make_pair(x,y));
  }

  sort(v.begin(), v.end());


  UnionFind tree(N);
  vector<pair<int,int>> ans;
  ll min_val = 0;
  for(int i = 0; i < M; i++){
    ll weight = (ll)v[i].first;
    int s = v[i].second.first;
    int t = v[i].second.second;

    if(tree.root(s) == tree.root(t)){
      continue;
    } else { 
      min_val += weight;
      tree.unionSet(s,t);
    }
  }
  cout << min_val << endl;
}
//