﻿ Ningbo University of Technology Online Judge :: Good Bye 2015 (One University One Question) Round III :: String in the tree
• ### [C] String in the tree

• 时间限制: 2000 ms　内存限制: 262144 K
• 问题描述
• You are given a tree which has n nodes, the root’s id is 1 and each node has an lowercase latter.

It is clear that we can get n roads from the root, each road forms a road string. Please calculate the number of different substrings in each road string.

• 输入
• Input starts with an integer T (T <= 20) denoting the number of test case.
For each test case, n (1 <= n <= 10000) is given.
Next n - 1 lines contain two integers u and v (1 <= u, v <= n), denoting an edge.
The next line contains a string whose length is equal to n, the ith letter is belong to the node whose id is i.
• 输出
• For each test case, output n lines, each line is the number of different substrings in this node’s road string.
• 样例输入
• ```3
3
1 2
2 3
abc
3
1 2
2 3
aaa
3
1 2
2 3
aab
```
• 样例输出
• ```1
3
6
1
2
3
1
2
5```
• 提示
• `无`
• 来源
• `本站或者转载`
• 操作
﻿ 