Trie in Tina Town | BestCoder Round #51 (div.2)

题目描述

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.

输入解释

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$

输出解释

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$

输入样例

2
5
a 0
a 1
a 2
b 1
b 4
5
a 0
a 1
a 2
b 1
a 4

输出样例

14
15

提示

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.

来自杭电HDUOJ的附加信息

Recommend

hujie

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 BestCoder Round #51 (div.2)

源链接： HDU-5394

最后修改于 2020-10-25T23:22:18+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
16000/8000MS(Java/Others)	524288/524288K(Java/Others)