#P5382. 走路

    ID: 4394 传统题 1000ms 1024MiB 尝试: 55 已通过: 22 难度: 8 上传者: 标签>难度分类提高+/省选-动态规划DAG 动态规划枚举与搜索折半枚举全子集枚举深度优先搜索离线与分治回滚维护状态数论Miller–RabinPollard–Rho快速幂快速乘防溢出CF2500

走路

走路

题目描述

白兔有一棵 nn 个点的树,以 11 号点为根。点 ii 的权值为 vali\mathrm{val}_i。

若 aa 是 bb 的真祖先,且 valb∣vala\mathrm{val}_b\mid\mathrm{val}_a(即 valb\mathrm{val}_b 整除 vala\mathrm{val}_a),白兔就能从 aa 直接跳到 bb。

求从 11 号点跳若干步到达每个点的方案数。经过的点数不同,或者某一步到达的点不同,均视为不同的方案。留在 11 号点、不跳的方案有一种。

输入格式

从标准输入读入。第一行一个正整数 nn。

接下来 n−1n-1 行,每行两个点编号 a,ba,b,表示一条树边。

最后一行 nn 个整数,依次表示各点的权值。

输出格式

向标准输出写出 nn 行,第 ii 行表示到达 ii 号点的方案数对 109+710^9+7 取模的结果。

样例文件

原赛题下发了一个独立样例文件。

数据范围

  • 对于 30%30\% 的数据,n≤5000n\le5000。
  • 对于另 10%10\% 的数据,每个点权值的不同质因子不超过一个。
  • 对于另 20%20\% 的数据,val1≤109\mathrm{val}_1\le10^9。
  • 对于另 20%20\% 的数据,树是一条链。
  • 对于全部数据,1≤n≤1051\le n\le10^5,val1≤1018\mathrm{val}_1\le10^{18}。保证每个点的权值都是 val1\mathrm{val}_1 的约数。