时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
小睿睿和小熙熙是很好的朋友，他们的学校有n个教室，教室间有n-1条路径且任意教室互相联通，每个教室给他们带来的愉悦值为val[i]，每天他们会选择在两个不同的教室(i,j)间的简单路径上秀恩爱，并给在lca(i,j)教室的人带来gcd(val[i],val[j])的伤害。每个教室里的单身狗们想知道：能给他们带来最大伤害和对应的无序点对数有多少个
（对于叶子结点，最大伤害及对应的无序点对个数为0）
无序点对：(i,j)与(j,i)视作同一对
gcd(a,b)：a与b的最大公因数
（对于叶子结点，最大伤害及对应的无序点对个数为0）
无序点对：(i,j)与(j,i)视作同一对
gcd(a,b)：a与b的最大公因数
输入描述:
第1行1个整数n，表示教室个数
第2至n行，每行两个整数a,b，表示a,b间有一条边
第n+1行，共n个整数，表示第i个教室的权值为val[i]
输出描述:
共n行，每行2个整数，分别表示第i个点受到的最大伤害和对应的无序点对数
备注:
树以1号教室为根对于50%的数据，且树的形态随机生成
另有20%的数据，树的形态为一条链
对于100%的数据，