Palindromic path queries in a tree

impl Solution {
  pub fn palindrome_path(n: i32, edges: Vec<Vec<i32>>, s: String, queries: Vec<String>) -> Vec<bool> {
    let n = n as usize;
    let s_bytes: Vec<u8> = s.bytes().collect();

    // Build adjacency list
    let mut adj = vec![vec![]; n];
    for e in &edges {
      let u = e[0] as usize;
      let v = e[1] as usize;
      adj[u].push(v);
      adj[v].push(u);
    }

    // Euler tour
    let log_n = if n <= 1 { 2 } else { (n as f64).log2() as usize + 2 };
    let mut tin = vec![0usize; n];
    let mut tout = vec![0usize; n];
    let mut depth = vec![0usize; n];
    let mut parent = vec![vec![0usize; log_n]; n];
    let mut euler_order = Vec::with_capacity(2 * n);

    // Iterative DFS for Euler tour
    let mut stack: Vec<(usize, usize, bool)> = vec![(0, 0, false)];
    let mut visited = vec![false; n];
    while let Some((u, par, is_exit)) = stack.pop() {
      if is_exit {
        tout[u] = euler_order.len();
        euler_order.push((u, true)); // exit event
        continue;
      }
      if visited[u] { continue; }
      visited[u] = true;
      tin[u] = euler_order.len();
      euler_order.push((u, false)); // entry event
      parent[u][0] = par;
      for k in 1..log_n {
        parent[u][k] = parent[parent[u][k - 1]][k - 1];
      }

      stack.push((u, par, true)); // post-order marker
      for &v in adj[u].iter().rev() {
        if !visited[v] {
          depth[v] = depth[u] + 1;
          stack.push((v, u, false));
        }
      }
    }

    let euler_size = euler_order.len(); // = 2*n

    // LCA using binary lifting
    let is_ancestor = |u: usize, v: usize| -> bool {
      tin[u] <= tin[v] && tout[u] >= tout[v]
    };

    let lca = |mut u: usize, v: usize| -> usize {
      if is_ancestor(u, v) { return u; }
      if is_ancestor(v, u) { return v; }
      for k in (0..log_n).rev() {
        if !is_ancestor(parent[u][k], v) {
          u = parent[u][k];
        }
      }
      parent[u][0]
    };

    // BIT for XOR prefix over Euler tour
    // At tin[u]: XOR in mask[u] (entry)
    // At tout[u]: XOR in mask[u] (exit, to cancel)
    // prefix_xor up to tin[u] = xor of masks from root to u
    let mut bit = vec![0u32; euler_size + 2];

    let bit_update = |bit: &mut Vec<u32>, mut i: usize, val: u32| {
      i += 1; // 1-indexed
      while i <= euler_size {
        bit[i] ^= val;
        i += i & i.wrapping_neg();
      }
    };

    let bit_query = |bit: &Vec<u32>, mut i: usize| -> u32 {
      i += 1; // 1-indexed
      let mut result = 0u32;
      while i > 0 {
        result ^= bit[i];
        i -= i & i.wrapping_neg();
      }
      result
    };

    // Initialize
    let mut masks = vec![0u32; n];
    for i in 0..n {
      masks[i] = 1 << (s_bytes[i] - b'a');
      bit_update(&mut bit, tin[i], masks[i]);
      bit_update(&mut bit, tout[i], masks[i]);
    }

    // xor_to_root(u) = bit_query(tin[u])
    // path_xor(u,v) = xor_to_root(u) ^ xor_to_root(v) ^ mask(lca(u,v))

    let mut result = Vec::new();

    for q in &queries {
      let parts: Vec<&str> = q.split_whitespace().collect();
      if parts[0] == "update" {
        let u = parts[1].parse::<usize>().unwrap();
        let c = parts[2].as_bytes()[0];
        let new_mask = 1u32 << (c - b'a');
        let old_mask = masks[u];
        let diff = old_mask ^ new_mask;
        bit_update(&mut bit, tin[u], diff);
        bit_update(&mut bit, tout[u], diff);
        masks[u] = new_mask;
      } else {
        let u = parts[1].parse::<usize>().unwrap();
        let v = parts[2].parse::<usize>().unwrap();
        let l = lca(u, v);
        let path_mask = bit_query(&bit, tin[u]) ^ bit_query(&bit, tin[v]) ^ masks[l];
        result.push(path_mask.count_ones() <= 1);
      }
    }

    result
  }
}