2791. Count Paths That Can Form a Palindrome in a Tree Hard

1/**
2 * [2791] Count Paths That Can Form a Palindrome in a Tree
3 *
4 * 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.
5 * 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.
6 * 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.
7 * A string is a palindrome when it reads the same backwards as forwards.
8 *  
9 * <strong class="example">Example 1:
10 * <img alt="" src="https://assets.leetcode.com/uploads/2023/07/15/treedrawio-8drawio.png" style="width: 281px; height: 181px;" />
11 * 
12 * Input: parent = [-1,0,0,1,1,2], s = "acaabc"
13 * Output: 8
14 * Explanation: The valid pairs are:
15 * - All the pairs (0,1), (0,2), (1,3), (1,4) and (2,5) result in one character which is always a palindrome.
16 * - The pair (2,3) result in the string "aca" which is a palindrome.
17 * - The pair (1,5) result in the string "cac" which is a palindrome.
18 * - The pair (3,5) result in the string "acac" which can be rearranged into the palindrome "acca".
19 * 
20 * <strong class="example">Example 2:
21 * 
22 * Input: parent = [-1,0,0,0,0], s = "aaaaa"
23 * Output: 10
24 * Explanation: Any pair of nodes (u,v) where u < v is valid.
25 * 
26 *  
27 * Constraints:
28 * 
29 * 	n == parent.length == s.length
30 * 	1 <= n <= 10^5
31 * 	0 <= parent[i] <= n - 1 for all i >= 1
32 * 	parent[0] == -1
33 * 	parent represents a valid tree.
34 * 	s consists of only lowercase English letters.
35 * 
36 */
37pub struct Solution {}
38
39// problem: https://leetcode.com/problems/count-paths-that-can-form-a-palindrome-in-a-tree/
40// discuss: https://leetcode.com/problems/count-paths-that-can-form-a-palindrome-in-a-tree/discuss/?currentPage=1&orderBy=most_votes&query=
41
42// submission codes start here
43
44impl Solution {
45    pub fn count_palindrome_paths(parent: Vec<i32>, s: String) -> i64 {
46        
47    }
48}
49
50// submission codes end
51
52#[cfg(test)]
53mod tests {
54    use super::*;
55
56    #[test]
57    fn test_2791() {
58    }
59}
60