#6159. 「美团 CodeM 初赛 Round A」最长树链

内存限制:512 MiB 时间限制:500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

Mr. Walker 最近在研究树,尤其是最长树链问题。现在树中的每个点都有一个值,他想在树中找出最长的链,使得这条链上对应点的值的最大公约数不等于 1 。请求出这条最长的树链的长度。

输入格式

第一行一个整数 n ,表示点的个数。
接下来 n-1 行,每行两个整数 x,y 表示 x,y 之间有边。
数据保证给出的是一棵树。
接下来一行 n 个整数表示每个点对应的权值 a_i

输出格式

输出一个整数,表示这条树链的长度。

样例

样例输入

4
1 2
1 3
2 4
6 4 5 2

样例输出

3

数据范围与提示

1 \leq n \leq 10^5, 1 \leq a_i \leq 10^9