• [1653] 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
  • 提示
  • 来源
  • 本站或者转载
  • 操作

显示春菜