A5986. 「美团 CodeM 初赛 Round A」最长树链
编程题
普及+/提高
知识点
题目描述
Mr. Walker 最近在研究树，尤其是最长树链问题。现在树中的每个点都有一个值，他想在树中找出最长的链，使得这条链上对应点的值的最大公约数不等于$1$。请求出这条最长的树链的长度。
输入格式
第一行一个整数 $n$，表示点的个数。
接下来 $n-1$ 行，每行两个整数 $x,y$ 表示 $x,y$ 之间有边。
数据保证给出的是一棵树。
接下来一行 $n$ 个整数表示每个点对应的权值 $a_i$。
接下来 $n-1$ 行，每行两个整数 $x,y$ 表示 $x,y$ 之间有边。
数据保证给出的是一棵树。
接下来一行 $n$ 个整数表示每个点对应的权值 $a_i$。
输出格式
输出一个整数，表示这条树链的长度。
输入输出样例
输入 #1
4 1 2 1 3 2 4 6 4 5 2
输出 #1
3
说明/提示
$1 \leq n \leq 10^5, 1 \leq a_i \leq 10^9$。