pub mod chminmax { pub fn chmin(a: &mut T, b: &T) -> bool { if *a > *b { *a = *b; true } else { false } } pub fn chmax(a: &mut T, b: &T) -> bool { if *a < *b { *a = *b; true } else { false } } } pub mod lower_bound { pub fn lower_bound(list: &[T], val: &T) -> usize { let mut l = 0; let mut r = list.len(); while l < r { let x = (l + r) / 2; match list[x].cmp(val) { std::cmp::Ordering::Less => { l = x + 1; } std::cmp::Ordering::Equal | std::cmp::Ordering::Greater => { r = x; } } } l } pub fn upper_bound(list: &[T], val: &T) -> usize { let mut l = 0; let mut r = list.len(); while l < r { let x = (l + r) / 2; match list[x].cmp(val) { std::cmp::Ordering::Less | std::cmp::Ordering::Equal => { l = x + 1; } std::cmp::Ordering::Greater => { r = x; } } } l } } pub mod scanner { pub struct Scanner { buf: Vec, } impl Scanner { pub fn new() -> Self { Self { buf: vec![] } } pub fn new_from(source: &str) -> Self { let source = String::from(source); let buf = Self::split(source); Self { buf } } pub fn next(&mut self) -> T { loop { if let Some(x) = self.buf.pop() { return x.parse().ok().expect(""); } let mut source = String::new(); std::io::stdin().read_line(&mut source).expect(""); self.buf = Self::split(source); } } fn split(source: String) -> Vec { source .split_whitespace() .rev() .map(String::from) .collect::>() } } } use std::collections::VecDeque; use crate::{chminmax::chmax, lower_bound::upper_bound, scanner::Scanner}; fn main() { let mut scanner = Scanner::new(); let t: usize = 1; for _ in 0..t { solve(&mut scanner); } } fn solve(scanner: &mut Scanner) { let n: usize = scanner.next(); let mut g = vec![vec![]; n]; for v in 2..=n { let l: usize = scanner.next(); let u: usize = scanner.next(); g[u - 1].push((v - 1, l)); } let mut que = VecDeque::new(); que.push_back(0); let mut res1: Vec<(usize, usize)> = vec![(1, 1)]; let mut res2: Vec = vec![-1; n]; res2[0] = 1; while let Some(u) = que.pop_front() { for &(v, l) in g[u].iter() { if res2[u] == -1 { continue; } let now = l.max(res2[u] as usize) as isize; chmax(&mut res2[v], &now); res1.push((res2[v] as usize, v)); que.push_back(v); } } res1.sort(); let q: usize = scanner.next(); for _ in 0..q { let t: usize = scanner.next(); if t == 1 { let x: usize = scanner.next(); println!("{}", upper_bound(&res1, &(x, !0))); } else { let y: usize = scanner.next(); println!("{}", res2[y - 1]); } } }