Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
 Register new ID

Another Letter Tree

Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 433    Accepted Submission(s): 98

Problem Description
A letter tree is given on this page (HDOJ 4601).

Another letter tree of N nodes is now given, where each node is assigned to a lowercase letter. When making a tour from a node to another, one should always follow the shortest path between them. That is, no nodes should be visited twice during his tour.

After one travels along a path, he will obtain a Path String formed by the letters assigned to nodes that he just moves past. The string exactly records all nodes in the order he visits.

Now we’re faced with the problem. Initially we have a string S0 and totally Q queries each in a shape of (u, v). For each query, we make a tour from u to v and obtain a Path String Suv , and your task is to calculate how many times that S0 occurs as a subsequence of Suv . For example, “ab” occurs 3 times in “abab” as a subsequence.

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For instance, “abc” and “ec” are both subsequence of “adebc”, while “ba” and “ed” are not.

The answer might be large, and thus you’re only required to output it modulo 10007.

The input consists of several test cases. The number of test cases T (T<=5) occurs in the first line of input.

For each test case:
The first line consists of two integers N and Q(1<=N, Q<=50000), denoting the number of nodes and queries, respectively.
Each of the following N - 1 lines contains a pair of integers u, v(1<=u, v<=N ), denoting an edge between node u and v.
The following line contains a string of N lowercase letters, where the ith denotes the letter represented by the ith node.
The following line contains S0(1<=|S0|<=30).
The following Q lines describe all queries, each of which describes the start node u and destination node v.

For each query, output the required answer modulo 10007 in a line.

Sample Input
2 6 3 1 2 1 3 2 4 2 5 3 6 abbaaa ab 4 5 4 6 2 1 6 3 1 2 1 3 2 4 2 5 3 6 abbaaa aba 4 5 4 6 2 1

Sample Output
1 3 0 1 4 0



Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-07-14 08:55:30, Gzip enabled