#P5382. 走路
走路
走路
题目描述
白兔有一棵 个点的树,以 号点为根。点 的权值为 。
若 是 的真祖先,且 (即 整除 ),白兔就能从 直接跳到 。
求从 号点跳若干步到达每个点的方案数。经过的点数不同,或者某一步到达的点不同,均视为不同的方案。留在 号点、不跳的方案有一种。
输入格式
从标准输入读入。第一行一个正整数 。
接下来 行,每行两个点编号 ,表示一条树边。
最后一行 个整数,依次表示各点的权值。
输出格式
向标准输出写出 行,第 行表示到达 号点的方案数对 取模的结果。
样例文件
原赛题下发了一个独立样例文件。
数据范围
- 对于 的数据,。
- 对于另 的数据,每个点权值的不同质因子不超过一个。
- 对于另 的数据,。
- 对于另 的数据,树是一条链。
- 对于全部数据,,。保证每个点的权值都是 的约数。