## https://yukicoder.me/problems/no/2325 from collections import deque MAX_INT = 10 ** 18 class BinaryIndexTree: """ フェニック木(BinaryIndexTree)の基本的な機能を実装したクラス """ def __init__(self, size): self.size = size self.array = [0] * (size + 1) def add(self, x, a): index = x while index <= self.size: self.array[index] += a index += index & (-index) def sum(self, x): index = x ans = 0 while index > 0: ans += self.array[index] index -= index & (-index) return ans def least_upper_bound(self, value): if self.sum(self.size) < value: return -1 elif value <= 0: return 0 m = 1 while m < self.size: m *= 2 k = 0 k_sum = 0 while m > 0: k0 = k + m if k0 < self.size: if k_sum + self.array[k0] < value: k_sum += self.array[k0] k += m m //= 2 if k < self.size: return k + 1 else: return -1 def main(): N = int(input()) la = [] for _ in range(N - 1): l, a = map(int, input().split()) la.append((l, a - 1)) Q = int(input()) queries = [] for _ in range(Q): t, x = map(int, input().split()) queries.append((t, x)) # トポロジカルソートとDP next_nodes= [[] for _ in range(N)] levels = [-1] * N levels[0] = 0 in_degree = [0] * N for i in range(N - 1): l, a = la[i] levels[i + 1] = l next_nodes[a].append(i + 1) in_degree[i + 1] += 1 dp = [MAX_INT] * N queue = deque() for i in range(N): if in_degree[i] == 0: queue.append(i) dp[i] = levels[i] while len(queue) > 0: v = queue.popleft() for w in next_nodes[v]: in_degree[w] -= 1 if dp[w] == MAX_INT: dp[w] = levels[w] dp[w] = max(dp[v], dp[w]) if in_degree[w] == 0: queue.append(w) # レベルXが覚えられる技をカウントするためのもの a_map = {} for i in range(N): d = dp[i] if d < MAX_INT: if d not in a_map: a_map[d] = 0 a_map[d] += 1 a_array = [(key, value) for key, value in a_map.items()] a_array.sort(key=lambda x : x[0]) a_cum_values = [0] * len(a_array) a = 0 for i in range(len(a_array)): a += a_array[i][1] a_cum_values[i] = a # 実際の計算 for t, x in queries: if t == 2: x -= 1 v = dp[x] if v == MAX_INT: print(-1) else: print(v) else: low = 0 high = len(a_array) - 1 while high - low > 1: mid = (high + low) // 2 if a_array[mid][0] <= x: low = mid else: high = mid if a_array[high][0] <= x: print(a_cum_values[high]) else: print(a_cum_values[low]) if __name__ == "__main__": main()