n junctions numbered from 0 to n - 1, with junction 0 as the root. The array parents describes the tree: parents[i] is the parent of junction i, and parents[0] = -1.
Every trail is marked with a letter: labels[i] is the letter on the trail between i and parents[i]. The character labels[0] means nothing. The string labels may be longer than n; any extra letters at the end belong to no trail.
Count the pairs of junctions (u, v) with u < v such that the letters along the path from u to v can be rearranged into a palindrome (a string that reads the same both ways).parents=[-1, 0, 0, 1], labels='xabb' → 4
The pairs (0, 1) give "a", (0, 2) give "b", (1, 3) give "b", and (2, 3) follows 2 → 0 → 1 → 3 for "bab". The paths (0, 3) and (1, 2) give "ab", which cannot be rearranged into a palindrome.
parents=[-1, 0, 1], labels='zcd' → 2
The root's letter labels[0] plays no part. Neighbouring nodes give one letter each, while the path from 0 to 2 gives "cd".
parents=[-1], labels='q' → 0
parents describes a valid treelabels consists of lowercase English lettersparents=[-1, 0, 0, 1], labels='xabb'
4
Run checks the first 3 tests in your browser. Submit checks all 52 tests on the server, hidden ones included.