palindromic-path-queries-in-a-tree

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] = [ui, vi] indicates an undirected edge between nodes ui and vi.

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.

You are also given a string array queries, where each queries[i] is either:

• "update ui c": Change the character at node ui to c. Formally, update s[ui] = c.


• "query ui vi": Determine whether the string formed by the characters on the unique path from ui to vi (inclusive) can be rearranged into a palindrome.

Return a boolean array answer, where answer[j] is true if the jth query of type "query ui vi"​​​​​​​ can be rearranged into a palindrome, and false otherwise.

Example 1:

Input: n = 3, edges = [[0,1],[1,2]], s = "aac", queries = ["query 0 2","update 1 b","query 0 2"]

Output: [true,false]

Explanation:

• "query 0 2": Path 0 → 1 → 2 gives "aac", which can be rearranged to form "aca", a palindrome. Thus, answer[0] = true.


• "update 1 b": Update node 1 to 'b', now s = "abc".


• "query 0 2": Path characters are "abc", which cannot be rearranged to form a palindrome. Thus, answer[1] = false.

Thus, answer = [true, false].

Example 2:

Input: n = 4, edges = [[0,1],[0,2],[0,3]], s = "abca", queries = ["query 1 2","update 0 b","query 2 3","update 3 a","query 1 3"]

Output: [false,false,true]

Explanation:

• "query 1 2": Path 1 → 0 → 2 gives "bac", which cannot be rearranged to form a palindrome. Thus, answer[0] = false.


• "update 0 b": Update node 0 to 'b', now s = "bbca".


• "query 2 3": Path 2 → 0 → 3 gives "cba", which cannot be rearranged to form a palindrome. Thus, answer[1] = false.


• "update 3 a": Update node 3 to 'a', s = "bbca".


• "query 1 3": Path 1 → 0 → 3 gives "bba", which can be rearranged to form "bab", a palindrome. Thus, answer[2] = true.

Thus, answer = [false, false, true].

Constraints:

• 1 <= n == s.length <= 5 * 104


• edges.length == n - 1


• edges[i] = [ui, vi]


• 0 <= ui, vi <= n - 1


• s consists of lowercase English letters.


• The input is generated such that edges represents a valid tree.


• 1 <= queries.length <= 5 * 104​​​​​​​
  
  
  
  • queries[i] = "update ui c" or
  
  
  • queries[i] = "query ui vi"
  
  
  • 0 <= ui, vi <= n - 1
  
  
  • c is a lowercase English letter.