#P8920. [2020年省队模拟]比赛题目背景

    ID: 9013 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-动态规划数位 DP自动机 DP树算法子树转区间计数 DP模拟与实现技巧预计算转移CF2700

[2020年省队模拟]比赛题目背景

比赛题目背景

题目描述

给定一棵以1为根的树,节点 ii 上有数字 di∈[0,9]d_i\in[0,9]。选择一个包含根的连通节点集合,在这个集合形成的子树中,按深度优先遍历的访问次序拼接所有数字。遍历同一节点的儿子时,按节点编号从小到大访问。

定义 maxdigit(x)maxdigit(x) 为正整数 xx 十进制表示中的最大数位。序列满足

$$a_1=1,\qquad a_i=a_{i-1}+maxdigit(a_{i-1})\quad(i>1)。$$

拼接后的字符串按普通十进制整数取值,忽略前导零。例如 01 表示整数 1,属于序列;000 表示整数 0,不属于序列。不同的连通节点集合分别计数,即使它们得到同一整数。

如果拼接所得的数在该序列中出现,则该连通集合可以通关。求可通关集合数,模 109+710^9+7。

输入格式

第一行整数 TT。每组先输入正整数 nn,接下来 n−1n-1 行各两个整数表示树边,最后一行 nn 个0到9的整数 did_i。

输出格式

每组输出一行答案。

样例输入1

2
3
1 2
2 3
1 6 4
5
1 2
1 3
2 4
3 5
2 2 2 2 2

样例输出1

3
6

数据范围

T≤10T\le10,所有数据的 nn 之和不超过500。

子任务1占10分,n≤5n\le5;子任务2占30分,n≤50n\le50;子任务3占20分,第 ii 条边连接 i,i+1i,i+1;子任务4占40分,无额外限制。