Trie in Tina Town

Accepts: 0
Submissions: 18
Time Limit: 8000/4000 MS (Java/Others)
Memory Limit: 524288/524288 K (Java/Others)
Problem Description
Tina Town is a friendly place. People there care about each other. A trie which was planted by the first mayor of Tina Town grows in the center of the town. We define a palindrome substring in a trie a string that is a suffix of a string which the path from the root to any node represents and the string is a palindrome. Two palindromes are different if and only if their positions are different. Now, Tina wants to know the sum of the length of all palindrome substrings. Tina didn*t know the answer so she asked you to find out the answer for her.
Input
The first line contains a integer 每 number of cases For each case, the first line is an integer $N$ representing the number of nodes in trie except the root. The following $N$ lines contains a letter between $a$ and $d$ 每 the letter that node $n[i]$ stores and a number $f[i]$ 每 the index of $n[i]$*s father. It*s guaranteed that $fa[i] \leq i$. If $fa[i] = 0$ n[i] is the root. $T \leq 10, N \leq 2*{10}^6$
Output
The first line contains a integer 每 number of cases For each case, the first line is an integer $N$ representing the number of nodes in trie except the root. The following $N$ lines contains a letter between $a$ and $d$ 每 the letter that node $n[i]$ stores and a number $f[i]$ 每 the index of $n[i]$*s father. It*s guaranteed that $fa[i] \leq i$. If $fa[i] = 0$ n[i] is the root. $T \leq 10, N \leq 2*{10}^6$
Sample Input
2
5
a 0
a 1
a 2
b 1
b 4
5
a 0
a 1
a 2
b 1
a 4
Sample Output
14
15
Hint
The first test case is a trie like this: aaa *1 -> 3 aa *2 -> 4 a *3-> 3 b *2-> 2 bb *1- > 2 3+4+3+2+2 = 14 The second test case: aaa *1 -> 3 aba *1 -> 3 a *4 -> 4 b *1 -> 1 aa *2 -> 4 3+3+4+1+4 = 15 If the stack size is too small, you can submit it in C++ and add &#pragma comment(linker, "/STACK:102400000,102400000§)* at the head of your program. Large input, recommend to use fast I/O.