Count paths that can form a palindrome in a tree

Dynamic Programming Bit Manipulation Tree Depth-First Search Bitmask

48.5% acceptance

Feb 25, 2026

443

You are given a tree (i.e. a connected, undirected graph that has no cycles) rooted at node 0 consisting of n nodes numbered from 0 to n - 1. The tree is represented by a 0-indexed array parent of size n, where parent[i] is the parent of node i. Since node 0 is the root, parent[0] == -1. You are also given a string s of length n, where s[i] is the character assigned to the edge between i and parent[i]. s[0] can be ignored. Return the number of pairs of nodes (u, v) such that u < v and the characters assigned to edges on the path from u to v can be rearranged to form a palindrome. A string is a palindrome when it reads the same backwards as forwards.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn count_palindrome_paths(parent: Vec<i32>, s: String) -> i64 {
    use std::collections::{HashMap, VecDeque};
    let n = parent.len();
    let s = s.as_bytes();
    // Build children list for BFS traversal
    let mut children: Vec<Vec<usize>> = vec![vec![]; n];
    for i in 1..n {
      children[parent[i] as usize].push(i);
    }
    // BFS to compute XOR mask from root to each node (handles any parent index ordering)
    let mut masks = vec![0u32; n];
    let mut queue = VecDeque::new();
    queue.push_back(0usize);
    while let Some(node) = queue.pop_front() {
      for &child in &children[node] {
        let ch = (s[child] - b'a') as u32;
        masks[child] = masks[node] ^ (1 << ch);
        queue.push_back(child);
      }
    }
    // Count pairs where XOR of masks is 0 or power of 2
    let mut cnt: HashMap<u32, i64> = HashMap::new();
    for &m in &masks {
      *cnt.entry(m).or_insert(0) += 1;
    }
    let mut ans: i64 = 0;
    for (&m, &c) in &cnt {
      // Same mask: XOR = 0
      ans += c * (c - 1) / 2;
      // XOR = power of 2 (single bit different)
      for bit in 0..26u32 {
        let other = m ^ (1 << bit);
        if other > m {
          if let Some(&oc) = cnt.get(&other) {
            ans += c * oc;
          }
        }
      }
    }
    ans
  }
}