Problem 2988 --Yukikaze and Demons

2988: Yukikaze and Demons

上一题 正确率: $0.00\%$ 下一题
"
Time Limit $10$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $0$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

Description

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 kk. 

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!

Input

The input includes several test cases. 

The first line of the input contains one integer T(1≤T≤20)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)N(1≤N≤50000), k(1≤k≤100000)k(1≤k≤100000), and a digit string S(|S|=N)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 SS. 

For each of the next N−1N−1 lines, there are two space-separated integer u,vu,v, denoting a road connecting two vertex in the dragon forest.

Output

For each test case, print the answer in a line.

Sample Input复制

2
4 3 0123
1 2
1 4
3 1
2 10 50
1 2

Sample Output复制

6
2

提示

In the first example, there are 6 path can be cleared in a single strike:

$1,1-4,2-1-3,3-1-2,4,4-1$

推荐代码 查看2988 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC
第一挑战

赛题来源/所属竞赛 2019 Multi-University Training Contest 3 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛