import scala.collection.mutable import scala.collection.mutable.ArrayBuffer import scala.io.StdIn.* import scala.util.chaining.* import scala.math.* sealed trait State case class In(value: Int) extends State case class Out(value: Int) extends State class XorBit(val size: Int, initial: Array[Long]): private val array = initial.clone() for i <- 1 until size do val j = i + (~i & (i + 1)) if j < size then array(j) ^= array(i) def get(position: Int): Long = var result = 0L var pos = position while pos >= 0 do result ^= array(pos) pos -= ~pos & (pos + 1) result def add(position: Int, value: Long) = var pos = position while pos < size do array(pos) ^= value pos += ~pos & (pos + 1) class SumBit(val size: Int): private val array = Array.fill(size){0} def get(position: Int): Int = var pos = position var result = 0 while pos >= 0 do result += array(pos) pos -= ~pos & (pos + 1) result def add(position: Int, value: Int) = var pos = position while pos < size do array(pos) += value pos += ~pos & (pos + 1) @main def main = val n = readLine().toInt val edges = Array.fill(n - 1){ val Array(l, r, a) = readLine().split(' ') (l.toInt - 1, r.toInt - 1, a.toLong) } val q = readLine().toInt val queries = Array.fill(q){ val Array(t, x) = readLine().split(' ').map(_.toInt) (t, x - 1) } val graph = Array.fill(n){ArrayBuffer[(Int, Long)]()} for (l, r, a) <- edges do graph(l).addOne(r -> a) graph(r).addOne(l -> a) val parentEdge = Array.fill(n){-1L}.tap(_(0) = 0) val stack = mutable.Stack[State](In(0)) val inTime = Array.fill(n){0} val outTime = Array.fill(n){0} var time = 0 while stack.nonEmpty do stack.pop match case In(current) => inTime(current) = time stack.push(Out(current)) time += 1 for (to, a) <- graph(current) do if parentEdge(to) == -1L then parentEdge(to) = a stack.push(In(to)) case Out(current) => outTime(current) = time - 1 val eulerTour = Array.fill(n){0L} for i <- 0 until n do eulerTour(inTime(i)) = parentEdge(i) val bit = XorBit(n, eulerTour) val removed = SumBit(n) val result = ArrayBuffer[Long]() for (t, x) <- queries do t match case 1 => if removed.get(inTime(x)) == 0 then val xor = bit.get(outTime(x)) ^ bit.get(inTime(x) - 1) bit.add(inTime(x), xor) removed.add(inTime(x), 1) removed.add(outTime(x) + 1, -1) case 2 => result.addOne( if removed.get(inTime(x)) > 0 then 0L else bit.get(outTime(x)) ^ bit.get(inTime(x)) ) println(result.mkString("\n"))