I have a better approach.

The key problem is that:

Given several integers, with integer x appears c_x times, and some fixed integer m. It is asked that how many integers that are co-prime to m, i.e.

\sum_{i=1}^n c_i [ \gcd (i, m) = 1 ].

By Mobius inversion, we can get that

\sum_{i=1}^n c_i [ \gcd (i, m) = 1 ] = \sum_{d|m} \mu(d) \sum_{i=1}^{\lfloor n/d \rfloor} c_{id}.

Here we use some technique when we DFS the tree, for each vertex v, and every val_v's divisor d, maintain

s(d) = \sum_{i=1}^{\lfloor n/d \rfloor} c_{id},

and thus we can get s(d) in O(1) each time.

As above, an O(n \max_{k} \sigma(k)) algorithm is exhibited, where \sigma(k) means the number of k's divisors.

For more details, please see my

```
(https://www.codechef.com/viewsolution/15101950).
```