问题描述
Tina Town 是一个善良友好的地方.这里的每一个人都互相关心.
在Tina Town的镇中央，生长着一棵Tina Town第一任镇长种下的Trie.
我们定义一个Trie中的回文子串是根节点到任一节点所代表的字符串的一个后缀，并且它是一个回文串。其中两个回文子串不同当且仅当它们的位置不同.
现在，Tina想要知道它的所有回文子串长度的和。Tina当然不会算啦，所以她请你帮她算出这个答案。
输入描述
第一行一个整数$T$,表示数据组数.
以下每组数据,第一行一个整数$N$,表示Trie中除了根节点以外的节点个数.
接下来$N$行,第${i}$行先是一个${a}$到${d}$的字符,表示节点${n[i]}$储存的字符.再是一个数字${fa[i]}$,表示节点${n[i]}$的父亲编号.保证${fa[i]} \leq
{i}$.如果${fa[i]}=0$表示${n[i]}$的节点是根节点
$T\le 10,N\le 2\times 10^6$
输出描述
对于每组测试数据,输出一个整数$\tau$,表示它的所有不同的回文子串长度的和.
输入样例
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
Hint
第一组数据是这样的一棵Trie.
aaa 1条->3
aa 2条 ->4
a 3条 -> 3
b 2条 -> 2
bb 1条 ->2
3+4+3+2+2=14
第二组数据
aaa 1条->3
aba 1条->3
a 4条 -> 4
b 1条 -> 1
aa 2条 ->4
3+3+4+1+4=15
如果栈空间太小,可以用C++提交,在程序开头加一行
#pragma comment(linker, "/STACK:102400000,102400000")
因读入数据比较大,建议加上读入优化.
