编程介的小学生 2019-01-29 13:40 采纳率: 20.5%
浏览 178

问一个由字母表示的二叉树的问题,采用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

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
    • ¥15 python天天向上类似问题,但没有清零
    • ¥30 3天&7天&&15天&销量如何统计同一行
    • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
    • ¥15 C#调用python代码(python带有库)
    • ¥15 矩阵加法的规则是两个矩阵中对应位置的数的绝对值进行加和
    • ¥15 活动选择题。最多可以参加几个项目?
    • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
    • ¥15 vs2019中数据导出问题
    • ¥20 云服务Linux系统TCP-MSS值修改?