Written by zimujun

We know that \(\displaystyle\sum_{d|n}\varphi(d) = n\), so for each \(d\) in \(1, 2,\cdots, \max\{A_i\}\), we divide the tree in to connected components that have the divisor \(d\), then the answer is \(\displaystyle\sum_{d = 1} ^ {\max\{A_i\}}\varphi(d)\cdot sum(d)\), while \(sum(d)\) is sum of lengths of all the simple paths whose lengths are greater than \(2\) in the new graph. We can just use a simple DP to calculate it.

Time complexiety: \(O(n\sqrt{\max\{A_i\}})\)