Reduction and Growth
题目描述
对正整数变量 a,b,定义约减操作 D(a,b):将 a 改为 a/gcd(a,b),保持 b 不变。
在带正整数点权的树上,定义路径约减 Tu,v(a):按照从 u 到 v 的简单路径,依次用路径上每个节点的点权对变量 a 做一次约减。路径包含两个端点;u=v 时只约减一次。树上的点权不会被这个过程修改。
初始树只有节点 1,点权为 c1。依次加入节点 i=2,3,…,n:给定 ai,ui,vi,先在当前树上执行 Tui,vi(ai),以约减后的值作为新节点的点权 ci,再将节点 i 与节点 vi 连边。
输出最终所有节点的点权。
输入格式
第一行两个整数 n,c1。接下来 n−1 行,第 i−1 行给出加入节点 i 时的三个整数 ai,ui,vi。
1≤n≤2×105,1≤c1,ai≤106,1≤ui,vi<i。
输出格式
输出一行 n 个正整数,依次为 c1,c2,…,cn。
样例 1
输入
5 10
6 1 1
2 2 2
35 1 2
84 3 4
输出
10 3 2 7 2