3865: Yukikaze and Demons
内存限制：128 MB
时间限制：10.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
Yukikaze is facing a huge crisis!
Under the attack of a kind of demons, dragon eaters, the dragon forest is endanger. As a member of the Biscotti Knights Secret Squad, she must do something to save the dragon forest.
The road in the dragon forest forms an undirected tree. Every vertex is occupied by a demon with a type denoted by a decimal digit.
In one of her strike, she can sweep out all the enemy on the path if and only if the decimal number formed by concatenating the types of enemy on the path sequentially is divisible by a special number k.
The demons are destroying the forest! Time is limited, she needs to know how many path in the dragon forest can be cleared in a single strike of hers.
In this problem, a single vertex is considered as a path too!
Under the attack of a kind of demons, dragon eaters, the dragon forest is endanger. As a member of the Biscotti Knights Secret Squad, she must do something to save the dragon forest.
The road in the dragon forest forms an undirected tree. Every vertex is occupied by a demon with a type denoted by a decimal digit.
In one of her strike, she can sweep out all the enemy on the path if and only if the decimal number formed by concatenating the types of enemy on the path sequentially is divisible by a special number k.
The demons are destroying the forest! Time is limited, she needs to know how many path in the dragon forest can be cleared in a single strike of hers.
In this problem, a single vertex is considered as a path too!
输入
The input includes several test cases.
The first line of the input contains one integer T(1≤T≤20), denoting the number of test cases.
For each test case, the first line contains two space-separated integers N(1≤N≤50000), k(1≤k≤100000), and a digit string S(|S|=N). Denoting the number of vertex and the special number, and the decimal digits on every vertex. The decimal digit on the i-th vertex is the i-th character of S.
For each of the next N−1 lines, there are two space-separated integer u,v, denoting a road connecting two vertex in the dragon forest.
The first line of the input contains one integer T(1≤T≤20), denoting the number of test cases.
For each test case, the first line contains two space-separated integers N(1≤N≤50000), k(1≤k≤100000), and a digit string S(|S|=N). Denoting the number of vertex and the special number, and the decimal digits on every vertex. The decimal digit on the i-th vertex is the i-th character of S.
For each of the next N−1 lines, there are two space-separated integer u,v, denoting a road connecting two vertex in the dragon forest.
输出
For each test case, print the answer in a line.
样例输入 复制
2
4 3 0123
1 2
1 4
3 1
2 10 50
1 2样例输出 复制
6
2