use std::io::{Write, BufWriter}; // https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 macro_rules! input { ($($r:tt)*) => { let stdin = std::io::stdin(); let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next = move || -> String{ bytes.by_ref().map(|r|r.unwrap() as char) .skip_while(|c|c.is_whitespace()) .take_while(|c|!c.is_whitespace()) .collect() }; input_inner!{next, $($r)*} }; } macro_rules! input_inner { ($next:expr) => {}; ($next:expr,) => {}; ($next:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($next, $t); input_inner!{$next $($r)*} }; } macro_rules! read_value { ($next:expr, ( $($t:tt),* )) => { ($(read_value!($next, $t)),*) }; ($next:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($next, $t)).collect::>() }; ($next:expr, usize1) => (read_value!($next, usize) - 1); ($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error")); } // Lazy Segment Tree. This data structure is useful for fast folding and updating on intervals of an array // whose elements are elements of monoid T. Note that constructing this tree requires the identity // element of T and the operation of T. This is monomorphised, because of efficiency. T := i64, biop = max, upop = (+) // Reference: https://github.com/atcoder/ac-library/blob/master/atcoder/lazysegtree.hpp // Verified by: https://judge.yosupo.jp/submission/68794 // https://atcoder.jp/contests/joisc2021/submissions/27734236 pub trait ActionRing { type T: Clone + Copy; // data type U: Clone + Copy + PartialEq + Eq; // action fn biop(x: Self::T, y: Self::T) -> Self::T; fn update(x: Self::T, a: Self::U) -> Self::T; fn upop(fst: Self::U, snd: Self::U) -> Self::U; fn e() -> Self::T; fn upe() -> Self::U; // identity for upop } pub struct LazySegTree { n: usize, dep: usize, dat: Vec, lazy: Vec, } impl LazySegTree { pub fn new(n_: usize) -> Self { let mut n = 1; let mut dep = 0; while n < n_ { n *= 2; dep += 1; } // n is a power of 2 LazySegTree { n: n, dep: dep, dat: vec![R::e(); 2 * n], lazy: vec![R::upe(); n], } } #[allow(unused)] pub fn with(a: &[R::T]) -> Self { let mut ret = Self::new(a.len()); let n = ret.n; for i in 0..a.len() { ret.dat[n + i] = a[i]; } for i in (1..n).rev() { ret.update_node(i); } ret } #[inline] pub fn set(&mut self, idx: usize, x: R::T) { debug_assert!(idx < self.n); self.apply_any(idx, |_t| x); } #[inline] pub fn apply(&mut self, idx: usize, f: R::U) { debug_assert!(idx < self.n); self.apply_any(idx, |t| R::update(t, f)); } pub fn apply_any R::T>(&mut self, idx: usize, f: F) { debug_assert!(idx < self.n); let idx = idx + self.n; for i in (1..self.dep + 1).rev() { self.push(idx >> i); } self.dat[idx] = f(self.dat[idx]); for i in 1..self.dep + 1 { self.update_node(idx >> i); } } pub fn get(&mut self, idx: usize) -> R::T { debug_assert!(idx < self.n); let idx = idx + self.n; for i in (1..self.dep + 1).rev() { self.push(idx >> i); } self.dat[idx] } /* [l, r) (note: half-inclusive) */ #[inline] pub fn query(&mut self, l: usize, r: usize) -> R::T { debug_assert!(l <= r && r <= self.n); if l == r { return R::e(); } let mut l = l + self.n; let mut r = r + self.n; for i in (1..self.dep + 1).rev() { if ((l >> i) << i) != l { self.push(l >> i); } if ((r >> i) << i) != r { self.push((r - 1) >> i); } } let mut sml = R::e(); let mut smr = R::e(); while l < r { if (l & 1) != 0 { sml = R::biop(sml, self.dat[l]); l += 1; } if (r & 1) != 0 { r -= 1; smr = R::biop(self.dat[r], smr); } l >>= 1; r >>= 1; } R::biop(sml, smr) } /* ary[i] = upop(ary[i], v) for i in [l, r) (half-inclusive) */ #[inline] pub fn update(&mut self, l: usize, r: usize, f: R::U) { debug_assert!(l <= r && r <= self.n); if l == r { return; } let mut l = l + self.n; let mut r = r + self.n; for i in (1..self.dep + 1).rev() { if ((l >> i) << i) != l { self.push(l >> i); } if ((r >> i) << i) != r { self.push((r - 1) >> i); } } { let l2 = l; let r2 = r; while l < r { if (l & 1) != 0 { self.all_apply(l, f); l += 1; } if (r & 1) != 0 { r -= 1; self.all_apply(r, f); } l >>= 1; r >>= 1; } l = l2; r = r2; } for i in 1..self.dep + 1 { if ((l >> i) << i) != l { self.update_node(l >> i); } if ((r >> i) << i) != r { self.update_node((r - 1) >> i); } } } #[inline] fn update_node(&mut self, k: usize) { self.dat[k] = R::biop(self.dat[2 * k], self.dat[2 * k + 1]); } fn all_apply(&mut self, k: usize, f: R::U) { self.dat[k] = R::update(self.dat[k], f); if k < self.n { self.lazy[k] = R::upop(self.lazy[k], f); } } fn push(&mut self, k: usize) { let val = self.lazy[k]; self.all_apply(2 * k, val); self.all_apply(2 * k + 1, val); self.lazy[k] = R::upe(); } } enum AffineXor {} type AffineInt = i64; // Change here to change type impl ActionRing for AffineXor { type T = (AffineInt, AffineInt); // data, size type U = (AffineInt, AffineInt); // action, (a, b) |-> x |-> ax + b fn biop((x, s): Self::T, (y, t): Self::T) -> Self::T { (x ^ y, s + t) } fn update((x, s): Self::T, (a, b): Self::U) -> Self::T { (if s == 1 { b } else { 0 } ^ if a % 2 != 0 { x } else { 0 }, s) } fn upop(fst: Self::U, snd: Self::U) -> Self::U { let (a, b) = fst; let (c, d) = snd; (a * c, if c % 2 != 0 { b } else { 0 } ^ d) } fn e() -> Self::T { (0.into(), 0.into()) } fn upe() -> Self::U { // identity for upop (1.into(), 0.into()) } } // This function uses O(|g|) stack space. fn euler_tour(v: usize, par: usize, g: &[Vec], rng: &mut [(usize, usize)], cnt: &mut usize) { let me = *cnt; *cnt += 1; for &w in &g[v] { if w == par { continue; } euler_tour(w, v, g, rng, cnt); } rng[v] = (me, *cnt); } fn main() { // In order to avoid potential stack overflow, spawn a new thread. let stack_size = 104_857_600; // 100 MB let thd = std::thread::Builder::new().stack_size(stack_size); thd.spawn(|| solve()).unwrap().join().unwrap(); } fn dfs(v: usize, par: usize, g: &[Vec<(usize, i64)>], rng: &[(usize, usize)], val: &mut [i64], p: &mut [usize]) { p[v] = par; for &(w, c) in &g[v] { if w == par { continue; } val[w] = c; dfs(w, v, g, rng, val, p); } } fn solve() { let out = std::io::stdout(); let mut out = BufWriter::new(out.lock()); macro_rules! puts {($($format:tt)*) => (let _ = write!(out,$($format)*););} input! { n: usize, lra: [(usize1, usize1, i64); n - 1], q: usize, tx: [(i32, usize1); q], } let mut g = vec![vec![]; n]; let mut g_uw = vec![vec![]; n]; for &(l, r, a) in &lra { g_uw[l].push(r); g_uw[r].push(l); g[l].push((r, a)); g[r].push((l, a)); } let mut cnt = 0; let mut rng = vec![(0, 0); n]; euler_tour(0, n, &g_uw, &mut rng, &mut cnt); let mut val = vec![0; n]; let mut p = vec![0; n]; dfs(0, n, &g, &rng, &mut val, &mut p); let mut st = LazySegTree::::new(n); for i in 0..n { st.set(rng[i].0, (val[i], 1)); } for (t, x) in tx { if t == 1 { let (l, r) = rng[x]; st.update(l, r, (0, 0)); } else { let (l, r) = rng[x]; puts!("{}\n", st.query(l, r).0 ^ st.get(l).0); } } }