问一个由字母表示的二叉树的问题,采用C语言判断节点是否可以移动

Problem Description
A letter tree is a rooted tree that each edge is assigned to a lowercase letter. Node 1 is always considered the root. When making a tour in the tree, one is only allowed to step "down". In other word, if you're now on some node of the tree, you can only make a step to one of its children nodes.
After you travel along a path in the tree, you will obtain a Path String, which is formed by the letters assigned to edges that you just move along. The string exactly records all edges in the order of your visit.
Now we're faced with the problem. Located at some node u on the tree, your task is to move for exactly m steps and obtain a maximal lexicographic Path String. In order to avoid the huge output, you're only required to output the hash code of the string after it is transformed into a 26-base number, where 'a' for 0, 'b' for 1, …, 'z' for 25. For instance, "bac" = (678)26 for 678=1×262+0×261+2×260.

Input
The input contains several test cases.
An integer T(T≤20) will exist in the first line of input, indicating the number of test cases.
Each test case begins with an integer N(2≤N≤105), which denotes the number of nodes in the tree.
The following (N-1) lines describe the edges. An edge is described in the format of (u,v,c), which denotes an undirected edge between u and v with a lowercase letter c assigned.
The following line contains a single integer M(1≤M≤105), indicating the number of queries.
The following M lines, each with a pair of positive integers (u,m), describe the queries. (1≤m≤105)
The nodes are labeled from 1 to N.

Output
Output the hash code modulo 109+7 of the maximal lexicographic Path String for each query, one per line. If it's impossible to move for m steps, output IMPOSSIBLE.

Sample Input
1
6
1 2 a
1 3 b
2 4 c
2 5 b
2 6 c
3
1 1
1 2
3 1

Sample Output
1
2
IMPOSSIBLE

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐