3841. Palindromic Path Queries in a Tree

Topics: Principal , Array , String , Divide and Conquer , Bit Manipulation , Tree , Depth-First Search , Binary Indexed Tree , Segment Tree , Biweekly Contest 176

You are given an undirected tree with n nodes labeled 0 to n - 1 . This is represented by a 2D array edges of length n - 1 , where edges[i] = [uᵢ, vᵢ] indicates an undirected edge between nodes uᵢ and vᵢ .

You are also given a string s of length n consisting of lowercase English letters, where s[i] represents the character assigned to node i .

Return a boolean array answer , where answer[j] is true if the jᵗʰ query of type "query uᵢ vᵢ" can be rearranged into a palindrome , and false otherwise.

We solve the dynamic palindromic-path query problem on a tree using an Euler-tour representation combined with a Fenwick tree for range-XOR/point-query updates, binary lifting for LCA, and 26-bit integer masks to represent character parities.…