3841. Palindromic Path Queries in a Tree Hard

1/**
2 * [3841] Palindromic Path Queries in a Tree
3 *
4 * 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.
5 * 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.
6 * You are also given a string array queries, where each queries[i] is either:
7 * 
8 * 	"update ui c": Change the character at node ui to c. Formally, update s[ui] = c.
9 * 	"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 <span data-keyword="palindrome-string">palindrome</span>.
10 * 
11 * Return a boolean array answer, where answer[j] is true if the j^th query of type "query ui vi"​​​​​​​ can be rearranged into a palindrome, and false otherwise.
12 *  
13 * <strong class="example">Example 1:
14 * <div class="example-block">
15 * Input: <span class="example-io">n = 3, edges = [[0,1],[1,2]], s = "aac", queries = ["query 0 2","update 1 b","query 0 2"]</span>
16 * Output: <span class="example-io">[true,false]</span>
17 * Explanation:
18 * 
19 * 	"query 0 2": Path 0 &rarr; 1 &rarr; 2 gives "aac", which can be rearranged to form "aca", a palindrome. Thus, answer[0] = true.
20 * 	"update 1 b": Update node 1 to 'b', now s = "abc".
21 * 	"query 0 2": Path characters are "abc", which cannot be rearranged to form a palindrome. Thus, answer[1] = false.
22 * 
23 * Thus, answer = [true, false].
24 * </div>
25 * <strong class="example">Example 2:
26 * <div class="example-block">
27 * Input: <span class="example-io">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"]</span>
28 * Output: <span class="example-io">[false,false,true]</span>
29 * Explanation:
30 * 
31 * 	"query 1 2": Path 1 &rarr; 0 &rarr; 2 gives "bac", which cannot be rearranged to form a palindrome. Thus, answer[0] = false.
32 * 	"update 0 b": Update node 0 to 'b', now s = "bbca".
33 * 	"query 2 3": Path 2 &rarr; 0 &rarr; 3 gives "cba", which cannot be rearranged to form a palindrome. Thus, answer[1] = false.
34 * 	"update 3 a": Update node 3 to 'a', s = "bbca".
35 * 	"query 1 3": Path 1 &rarr; 0 &rarr; 3 gives "bba", which can be rearranged to form "bab", a palindrome. Thus, answer[2] = true.
36 * 
37 * Thus, answer = [false, false, true].
38 * </div>
39 *  
40 * Constraints:
41 * 
42 * 	1 <= n == s.length <= 5 * 10^4
43 * 	edges.length == n - 1
44 * 	edges[i] = [ui, vi]
45 * 	0 <= ui, vi <= n - 1
46 * 	s consists of lowercase English letters.
47 * 	The input is generated such that edges represents a valid tree.
48 * 	1 <= queries.length <= 5 * 10^4​​​​​​​
49 * 	
50 * 		queries[i] = "update ui c" or
51 * 		queries[i] = "query ui vi"
52 * 		0 <= ui, vi <= n - 1
53 * 		c is a lowercase English letter.
54 * 	
55 * 	
56 * 
57 */
58pub struct Solution {}
59
60// problem: https://leetcode.com/problems/palindromic-path-queries-in-a-tree/
61// discuss: https://leetcode.com/problems/palindromic-path-queries-in-a-tree/discuss/?currentPage=1&orderBy=most_votes&query=
62
63// submission codes start here
64
65impl Solution {
66    pub fn palindrome_path(n: i32, edges: Vec<Vec<i32>>, s: String, queries: Vec<String>) -> Vec<bool> {
67        vec![]
68    }
69}
70
71// submission codes end
72
73#[cfg(test)]
74mod tests {
75    use super::*;
76
77    #[test]
78    fn test_3841() {
79    }
80}
81