#include "bits/stdc++.h" #include using namespace std; #include "atcoder/all" using namespace atcoder; using i64 = long long; using u64 = unsigned long long; using ld = long double; using i_i = pair; using l_l = pair; using d_d = pair; using s_s = pair; using i_i_i = tuple; using i_i_i_i = tuple; using l_l_l = tuple; using l_l_l_l = tuple; using _bool = int; #define rep(i, n) for(i64 i = 0; i < n; i++) #define rep2(i, l, r) for(i64 i = l; i < r; i++) #define rrep(i, n) for(i64 i = n - 1; i >= 0; i--) #define rrep2(i, l, r) for(i64 i = r - 1; i >= l; i--) #define ifbit(n,k) ((n>>k)&1) //if kth bit of n is on then true (sitakara, 0-indexed) #define zpad(i) cout << setfill('0') << setw(i) #define dout cout << fixed << setprecision(10) #define douts(i) cout << fixed << setprecision(i) << scientific #define pcnt __builtin_popcount constexpr int INF = 2147483647; constexpr i64 I64F = 9223372036854775807; template bool chmax(T &l, const T &r) { if (l < r) { l = r; return true; } return false; } template bool chmin(T &l, const T &r) { if (l > r) { l = r; return true; } return false; } template pair ub(const vector &v, const T &key) { int ind = upper_bound(v.begin(), v.end(), key) - v.begin(); if (ind == (int)v.size()) return make_pair(0, false); return make_pair(ind, true); } template pair rub(const vector &v, const T &key) { int ind = upper_bound(v.rbegin(), v.rend(), key, [](const T & l, const T & r) { return l > r; }) - v.rbegin(); if (ind == (int)v.size()) return make_pair(0, false); return make_pair((int)v.size() - 1 - ind, true); } template pair lb(const vector &v, const T &key) { int ind = lower_bound(v.begin(), v.end(), key) - v.begin(); if (ind == (int)v.size()) return make_pair(0, false); return make_pair(ind, true); } template pair rlb(const vector &v, const T &key) { int ind = lower_bound(v.rbegin(), v.rend(), key, [](const T & l, const T & r) { return l > r; }) - v.rbegin(); if (ind == (int)v.size()) return make_pair(0, false); return make_pair((int)v.size() - 1 - ind, true); } void pu(vector> v) { for (int i = 0; i < v.size(); i++) { for (int j = 0; j < v[i].size(); j++) { cout << v[i][j]; } cout << endl; } } i64 max(i64 l, int r) { return max(l, (i64)r); } i64 max(int l, i64 r) { return max((i64)l, r); } void pu(int v) { cout << v << endl; } void pu(i64 v) { cout << v << endl; } void pu(double v) { cout << fixed << setprecision(14) << v << endl; } void pu(ld v) { cout << fixed << setprecision(14) << v << endl; } void pu(string v) { cout << v << endl; } void pu(modint998244353 v) { cout << v.val() << endl; } void pu(modint1000000007 v) { cout << v.val() << endl; } void pu(vector v) { rep(i, v.size()) cout << v[i] << (i + 1 == v.size() ? "\n" : " "); } void pu(vector v) { rep(i, v.size()) cout << v[i] << (i + 1 == v.size() ? "\n" : " "); } void pu(set v) { bool flag = false; for (auto dv : v) { if (flag) cout << " "; cout << dv; flag = true;} cout << endl;} void pu(set v) { bool flag = false; for (auto dv : v) { if (flag) cout << " "; cout << dv; flag = true;} cout << endl;} void pu(multiset v) { bool flag = false; for (auto dv : v) { if (flag) cout << " "; cout << dv; flag = true;} cout << endl; } void pu(multiset v) { bool flag = false; for (auto dv : v) { if (flag) cout << " "; cout << dv; flag = true;} cout << endl; } //comb i64 comb(const i64& n, const i64& k) { i64 ret = 1; for (i64 i = 1; i <= k; i++) { ret *= n + 1 - i; ret /= i; } return ret; } struct cord { //support coordinate compression public: cord() : cord(vector {}) {} explicit cord (const vector& v) : ov(v), cv(v) { set s(v.begin(), v.end()); int cnt = 0; for (auto x : s) { conv[x] = cnt++; } for (auto &x : cv) { x = conv[x]; } for (auto [k, u] : conv) { rconv[u] = k; } conv[I64F] = cnt; } //ex //index {0, 1, 2, 3, 4, 5} //original value {5, 9, 3, 1, 6, 3} //compressed value {2, 4, 1, 0, 3, 1} //input:index //output:compressed value i64 &operator[](int i) { assert(0 <= i and i < (int)cv.size()); return cv[i]; } //input:compressed value //output:original value i64 get(int v) { assert(rconv.find(v) != rconv.end()); return rconv[v]; } int size() const { return (int)rconv.size(); } //input:original value //output:index int lower_bound(i64 v) { return conv.lower_bound(v) -> second;} int upper_bound(i64 v) { return conv.upper_bound(v) -> second;} private: //original, compressed vector ov, cv; //key:original value, value:compressed value map conv; //key:compressed value, value:origirnal value map rconv; }; //factorial template class factorial { private: vector fact; vector ifact; public: factorial(const int& n) : fact(n + 1), ifact(n + 1) { fact[0] = 1; for (int i = 1; i <= n; i++) { fact[i] = fact[i - 1] * i; } ifact[n] = fact[n].inv(); for (int i = n; i >= 1; i--) { ifact[i - 1] = ifact[i] * i; } } T comb(const int& n, const int& k) { if (k < 0 or k > n) { return 0; } return fact[n] * ifact[k] * ifact[n - k]; } T get(const int& n) { return fact[n]; } T inv(const int& n) { return ifact[n]; } }; //lca template struct lca { public: lca(int n_) : n(n_), to(n), co(n), dep(n), costs(n) { l = 0; while ((1 << l) < n) { l++; } par = vector>(n + 1, vector(l, n)); } void add_edge(int a, int b, T c = 1) { to[a].push_back(b); co[a].push_back(c); to[b].push_back(a); co[b].push_back(c); } void init(int root_ = 0) { root = root_; dfs(root); for (int i = 0; i < l - 1; i++) { for (int v = 0; v < n; v++) { par[v][i + 1] = par[par[v][i]][i]; } } } int get(int a, int b) { if (dep[a] > dep[b]) { swap(a, b); } int gap = dep[b] - dep[a]; for (int i = l - 1; i >= 0; i--) { int len = 1 << i; if (gap >= len) { gap -= len; b = par[b][i]; } } if (a == b) { return a; } for (int i = l - 1; i >= 0; i--) { int na = par[a][i]; int nb = par[b][i]; if (na != nb) { a = na, b = nb; } } return par[a][0]; } T dist(int a, int b) { int c = get(a, b); return costs[a] + costs[b] - costs[c] * 2; } private: int n, root, l; vector> to; vector> co; //cost vector dep; vector costs; //costs sum vector> par; void dfs(int v, int d = 0, T c = 0, int p = -1) { if (p != -1) { par[v][0] = p; } dep[v] = d; costs[v] = c; for (int i = 0; i < to[v].size(); i++) { int u = to[v][i]; if (u == p) { continue; } dfs(u, d + 1, c + co[v][i], v); } } }; //matrix_ex template class matrix_ex { private: int n; vector> rec_relation; vector> multipl_sqare(const vector>& lhs, const vector>& rhs) { vector ret(n, vector(n, 0)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { ret[i][j] += lhs[i][k] * rhs[k][j]; } } } return ret; } vector multipl(const vector>& lhs, const vector& rhs) { vector ret(n, 0); for (int i = 0; i < n; i++) { for (int k = 0; k < n; k++) { ret[i] += lhs[i][k] * rhs[k]; } } return ret; } public: matrix_ex(const vector>& vec_in) : n(vec_in.size()) { rec_relation = vector>(n, vector(n)); rec_relation = vec_in; } vector get_ans(i64 t, const vector& vec_in) { vector ret(n, vector(n, 0)); for (int i = 0; i < n; i++) { ret[i][i] = 1; } while (t) { if ((t % 2LL) == 0LL) { rec_relation = multipl_sqare(rec_relation, rec_relation); t >>= 1LL; } else { ret = multipl_sqare(rec_relation, ret); t--; } } return multipl(ret, vec_in); } }; //prime struct prime { public: prime() : isp(1e7) {} explicit prime (int n) : _n(n), isp(vector<_bool>(n + 1, true)), mfact(vector(n + 1, -1)) { isp[0] = isp[1] = false; mfact[0] = mfact[1] = 1; for (int i = 2; i <= n; i++) { if (isp[i]) { ps.push_back(i); mfact[i] = i; for (int j = 2 * i; j <= n; j += i) { isp[j] = false; if (mfact[j] == -1) { mfact[j] = i; } } } } } vector fast_get(int n) { vector ret; assert(0 < n and n <= _n); int i = -1; while (n > 1) { if (i == -1 or ret[i].first != mfact[n]) { ret.push_back({mfact[n], 0}); i++; } n /= mfact[n]; ret[i].second++; } return ret; } vector get(i64 n) { vector ret; assert(0 < n and n <= ps.back() * ps.back()); int i = 0, cnt = -1; while (ps[i] * ps[i] <= n) { if (n % ps[i] == 0) { ret.push_back({ps[i], 1}); cnt++; n /= ps[i]; while (n % ps[i] == 0) { n /= ps[i]; ret[cnt].second++; } } i++; if (i == ps.size()) { break; } } if (n > 1) ret.push_back({n, 1}); return ret; } bool operator[](int n) { assert(0 < n and n <= _n); return isp[n]; } vector get_all(i64 n) { i64 i = 1; vector ret; while (i * i <= n) { if (n % i == 0) { ret.push_back(i); if (n / i != i) { ret.push_back(n / i); } } i++; } sort(ret.begin(), ret.end()); return ret; } private: int _n; vector<_bool> isp; //is-prime vector ps; //primes vector mfact; }; //rolling hash const unsigned bases[64] = {257, 262, 266, 275, 276, 281, 285, 290, 296, 302, 306, 310, 311, 313, 323, 333, 344, 345, 350, 357, 367, 370, 373, 402, 423, 425, 431, 440, 442, 443, 454, 457, 458, 462, 471, 478, 481, 487, 489, 492, 499, 501, 502, 503, 506, 514, 524, 532, 535, 541, 550, 552, 557, 559, 562, 563, 567, 570, 571, 580, 592, 597, 604, 612}; const u64 mod = 0x1fffffffffffffff, base = bases[chrono::duration_cast(chrono::system_clock::now().time_since_epoch()).count() & 63]; struct rollinghash { public: rollinghash() : rollinghash("") {} explicit rollinghash (const string &s) { i64 n = s.size(); hashed.assign(n + 1, 0); power.assign(n + 1, 0); power[0] = 1; for (i64 i = 0; i < n; i++) { power[i + 1] = mul(power[i], base); hashed[i + 1] = mul(hashed[i], base) + s[i]; if (hashed[i + 1] >= mod) { hashed[i + 1] -= mod; } } } u64 get(i64 l, i64 r) const { u64 ret = hashed[r] + mod - mul(hashed[l], power[r - l]); if (ret >= mod) { ret -= mod; } return ret; } u64 connect(u64 h1, u64 h2, i64 h2len) const { u64 ret = mul(h1, power[h2len]) + h2; if (ret >= mod) { ret -= mod; } return ret; } void connect(const string &s) { i64 n = hashed.size() - 1, m = s.size(); hashed.resize(n + m + 1); power.resize(n + m + 1); for (i64 i = n; i < n + m; i++) { power[i + 1] = mul(power[i], base); hashed[i + 1] = mul(hashed[i], base) + s[i - n]; if (hashed[i + 1] >= mod) { hashed[i + 1] -= mod; } } } i64 LCP(const rollinghash &b, i64 l1, i64 r1, i64 l2, i64 r2) { i64 len = min(r1 - l1, r2 - l2); i64 low = -1, high = len + 1; while (high - low > 1) { i64 mid = (low + high) / 2; if (get(l1, l1 + mid) == b.get(l2, l2 + mid)) { low = mid; } else { high = mid; } } return low; } private: vector hashed, power; static constexpr u64 mask(i64 a) { return (1ull << a) - 1; } inline u64 mul(u64 a, u64 b) const { u64 a31 = a >> 31, b31 = b >> 31; a &= mask(31); b &= mask(31); u64 x = a * b31 + b * a31; u64 ans = (a31 * b31 << 1) + (x >> 30) + ((x & mask(30)) << 31) + a * b; ans = (ans >> 61) + (ans & mod); if (ans >= mod) { ans -= mod; } return ans; } }; template vector> rot(const vector> &v) { vector> ret = v; int n = v.size(); rep(i, n) assert(n == v[i].size()); rep(i, n) { rep(j, n) { ret[i][j] = v[j][n - 1 - i]; } } return ret; } templatevoid warshall_floyd(T& co) { int n = co.size(); rep(k, n) rep(i, n) rep(j, n) { if (co[i][k] == INF) { continue; } if (co[k][j] == INF) { continue; } chmin(co[i][j], co[i][k] + co[k][j]); } } // end of template // *INDENT-ON* int main() { ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; cin >> n; scc_graph g(n); vector l(n); vector to(n, vector()); rep(i, n - 1) { int a; cin >> l[i + 1] >> a; a--; to[a].push_back(i + 1); g.add_edge(a, i + 1); } auto p = g.scc(); vector dp(n, -1); dp[0] = 0; // assert(p[0][0] == 0); for (auto v : p) { for (auto u : v) { if (dp[u] == -1) { continue; } chmax(dp[u], l[u]); for (auto w : to[u]) { chmax(dp[w], dp[u]); } } } map mp; for (auto d : dp) { if (d >= 0) { mp[d]++; } } int now = 0; for (auto& [k, v] : mp) { now += v; v = now; } int q; cin >> q; rep(i, q) { int op; cin >> op; if (op == 1) { int x; cin >> x; auto it = mp.upper_bound(x); cout << prev(it)->second << endl; } else { int y; cin >> y; cout << dp[y - 1] << endl; } } return 0; }