import std; void main () { int N = readln.chomp.to!int; auto L = new int[](N - 1); auto A = new int[](N - 1); foreach (i; 0 .. N - 1) { readln.read(L[i], A[i]); A[i]--; } // query1: レベルxである技を覚えられる <=> 前提技とその技に必要なレベルがx以下 // A[i] -> iの有向木を作って根側からレベルをchmaxするとわかる。あとは技1から到達可能なものを列挙しておき、二分探索 // query2: 可能かの判定はA[i] -> iの有向木で1からのパスが存在するかどうか // これはBFSでO(N)時間 // パスが一意であることに注意すると、必要な技レベルはその頂点を含めた必要レベルのmax // やはりchmaxしておくとわかる。 auto need = new int[](N); need[] = -1; auto graph = new int[][](N); foreach (i; 0 .. N - 1) { graph[A[i]] ~= i + 1; } void dfs (int pos) { foreach (to; graph[pos]) { need[to] = max(need[pos], L[to - 1]); dfs(to); } } need[0] = 0; dfs(0); auto levels = new int[](0); foreach (i; 0 .. N) { if (need[i] != -1) { levels ~= need[i]; } } levels.sort; int Q = readln.chomp.to!int; auto ans = new int[](Q); foreach (i; 0 .. Q) { auto input = readln.split.to!(int[]); int t = input[0]; if (t == 1) { int x = input[1]; ans[i] = levels.arrayBSearch!((int v) => v <= x)[0].length.to!int; } if (t == 2) { int y = input[1]; y--; ans[i] = need[y]; } } writefln("%(%s\n%)", ans); } void read (T...) (string S, ref T args) { import std.conv : to; import std.array : split; auto buf = S.split; foreach (i, ref arg; args) { arg = buf[i].to!(typeof(arg)); } } // 配列特化二分探索 // fun: T -> boolが必要。また、一度falseになったら後ろが必ずfalseになるような述語を仮定。 // 戻り値はスライス2個。 // それぞれB1, B2としたとき、 // B1の要素はfun(b1)がtrue // B2の要素はfun(b2)がfalse import std.traits; T[][2] arrayBSearch (alias fun, T) (T[] A) if (__traits(compiles, fun(T.init)) && is(typeof(fun(T.init)) == bool) ) { if (A.length == 0) { return [[], []]; } if (!fun(A[0])) { return [[], A[]]; } int l = 0, r = cast(int)(A.length); while (1 < r - l) { int mid = (l + r) / 2; if (fun(A[mid])) { l = mid; } else { r = mid; } } return [A[0 .. r], A[r .. $]]; }