Palindromic Communication Paths - Goldman Sachs IIIT Allahabad

Problem Preview

"### Problem You are given a rooted tree with N vertices numbered from 0 to N - 1, rooted at vertex 0. For every vertex i (1 ≤ i < N), you are given its parent parent[i]. Each edge from parent[i] to i is labeled with a lowercase English letter label[i]. (The root has no incoming edge.) A path is considered valid if the multiset of characters on its edges can be rearranged to form a palindrome. Your task is to determine the number of unordered pairs of vertices (u, v) (u < v) such that the unique simple path between u and v is valid. ### Input - N - parent[1] parent[2] ... parent[N-1] - s S is a string of length N, where S[0] is ignored and S[i] is the label of the edge (parent[i], i). ### Output Print a single integer — the number of valid pairs. ### Constraints - 2 ≤ N ≤ 2 × 10^5 - 0 ≤ parent[i] < i - S[i] is a lowercase English letter."