#P18069. Reduction and Growth

Reduction and Growth

Reduction and Growth

题目描述

对正整数变量 a,ba,b,定义约减操作 D(a,b)D(a,b):将 aa 改为 a/gcd⁡(a,b)a/\gcd(a,b),保持 bb 不变。

在带正整数点权的树上,定义路径约减 Tu,v(a)T_{u,v}(a):按照从 uu 到 vv 的简单路径,依次用路径上每个节点的点权对变量 aa 做一次约减。路径包含两个端点;u=vu=v 时只约减一次。树上的点权不会被这个过程修改。

初始树只有节点 11,点权为 c1c_1。依次加入节点 i=2,3,…,ni=2,3,\ldots,n:给定 ai,ui,via_i,u_i,v_i,先在当前树上执行 Tui,vi(ai)T_{u_i,v_i}(a_i),以约减后的值作为新节点的点权 cic_i,再将节点 ii 与节点 viv_i 连边。

输出最终所有节点的点权。

输入格式

第一行两个整数 n,c1n,c_1。接下来 n−1n-1 行,第 i−1i-1 行给出加入节点 ii 时的三个整数 ai,ui,via_i,u_i,v_i。

1≤n≤2×1051\le n\le2\times10^5,1≤c1,ai≤1061\le c_1,a_i\le10^6,1≤ui,vi<i1\le u_i,v_i<i。

输出格式

输出一行 nn 个正整数,依次为 c1,c2,…,cnc_1,c_2,\ldots,c_n。

样例 1

输入

5 10
6 1 1
2 2 2
35 1 2
84 3 4

输出

10 3 2 7 2