Find Palindromes

Problem Overview

• Rooted tree (root=1) with N nodes; each node has a lowercase character; answer Q queries.
• For query u, form S by post-order over u’s subtree, visiting children by increasing id; append each node’s C; ask if S is a palindrome.
• Input: N, N−1 edges, C[1..N], Q, then Q nodes u. Output: Q lines: 1 if palindromic, else 0.
• Constraints up to 200k; fast I/O; domain: tree traversal and string analysis for a coding interview problem.
• From Google interviews; a common interview question.