提出 #41147123

---

ソースコード 拡げる

#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll = long long;
const double pi = 3.14159265359;
const ll INF = 1LL << 60;

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;}

//using mint = modint998244353;
//using mint = modint1000000007;
//using mint = modint;  // mint::set_mod(p); later
//using mint = static_modint<1000000009>;

int main()
{
  cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

  int N;
  cin >> N;
  vector<int> p(N);
  for (int i = 1; i < N; i++){
    cin >> p[i];
    p[i]--;
  }

  dsu uf(N);
  vector<int> r(N); // r[i] = i を代表元とするような強連結成分内の最小頂点
  iota(r.begin(), r.end(), 0);

  auto get_min = [&](int i){ return r[uf.leader(i)]; };

  int Q;
  cin >> Q;

  for (int i = 0; i < Q; i++){
    int ty;
    cin >> ty;

    if (ty == 1){
      int u, v;
      cin >> u >> v;
      u--; v--;
      while (get_min(u) > v){
	int mn = get_min(u); // 現在の SCC の中での最小頂点
	int nr = get_min(p[mn]); // 一つ前の SCC の最小頂点
	r[uf.merge(mn, p[mn])] = nr;
      }
    } else {
      int x;
      cin >> x;
      x--;
      cout << get_min(x) + 1 << "\n";
    }
  }
  
  return 0;
}

提出情報

ジャッジ結果