Problem Link (Contest) - https://www.codechef.com/LOCAUG17/problems/GTREE
I tried to solve the above problem from LoC AUG 2017 and wrote a brute force solution (by doing a DFS from each node in its subtree) that fetched 30 pts but couldn’t come up with an approach to solve this problem completely.
Can someone explain how to solve this problem?
I didnt give any submissions on the problem… but I can write what i think is a correct solution.
So, first… flatten the tree into an array. So now the problem is to solve range queries where each query returns the number of non co-prime numbers.
First, compress the numbers so that they contain its prime factors only once. for example, 72 = 2 * 2 * 2 * 3 * 3
Write it as 2 * 3 – meaning that every unique prime factor is taken only once. So you can easily show that a number will contain at most 6 factors in this form. for that just take the product of the first 7 unique prime numbers and that will exceed 1e5, the max size of the number.
Now, maintain list of all the possible factors and their multiples that are present. Now this may seem to be N^2 as you are maintaining 1e5 sized array of vectors, but each number can have atmost 2^6 factors, so in all there can be at most 2^6 * N elements.
Now given a range, basically do a principle of inclusion and exclusion type thing, and binary search for the numbers present in the range, using the aforementioned lists that have been made. The whole factorization can be done in NlogN time using the smallest prime factor seiving technique, and the overall complexity should be about 2^6 * log^2 N per query approx.( this may be actually logN, i forgot 
). This should work within the given time limit.
I hope this was a correct solution.
i had similar idea but stuck at the inclusion and exclusion thing…(:
@rajashri_basu can you please explain the last paragraph a little more?
I checked a few solutions and they seem to be using the Möbius function, which I don’t know about. I’m reading up on it and if I am able to understand the solution I’ll explain it here.
How do we apply binary search in your last part , like what is the property that is monotonic here , I understood the property of inclusion and exclusion like suppose if our curr_subtree node has {2,3,5} as it’s unique prime divisor’s then we will use inclusion and exclusion principle to find like how many numbers are divisible in that range by atleast one of the numbers from our given list like we will find how_many_divisible_by(2)+how_many_divisible_by(3)+how_many_divisible_by(5)-how_many_divisible_by(2* 3)-how_many_divisible_by(2* 5)-how_many_divisible_by(3* 5)+how_many_divisible_by(2* 3* 5) in that range and u are saying that we can find the value of a how_many_divisible_by(x) by using binary search in that range but i don’t understand how to apply binary search .
There are do not need array and binary search. Simple dfs and use array with number of multiples present in upper nodes.
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.
By Mobius inversion, we can get that
Here we use some technique when we DFS the tree, for each vertex v, and every val_v's divisor d, maintain
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).@liouzhou_101 
Can you explain how you converted the problem to: “Given several integers, with integer x appears cx times, and some fixed integer m. It is asked that how many integers that are co-prime to m”
For every vertex x in the tree, it is asked that how many vertices y in the subtree of x such that \gcd (val_y, val_x) > 1.
It can be converted to that how many vertices y in the subtree of x such that \gcd (val_y, val_x) = 1 (The original problem’s complement.), where val_x is the m, and val_y are the integers x.
@liouzhou_101 How did you convert
∑d|mμ(d)∑i=1⌊n/d⌋cid
I have already this and this but not able to figure out how you converted to mobius inversion. Can you please explain that formula
@liouzhou_101 s(d) appears to be cnt[d] in your code, but s(d) is the number of times any multiple of d occurs whereas cnt[d] is just the number of times d appears. Am I getting something wrong?
cnt[d] is to calculate the number of times any multiples of d occurs, however, it is not that itself.
In my code:
void dfs(int x, int pre)
{
size[x] = 1;
ans[x] = 0;
for (auto d : divisor[a[x]])
{
++ cnt[d];
ans[x] -= u[d]*cnt[d];
}
for (auto y : v[x])
{
if (y == pre) continue;
dfs(y, x);
size[x] += size[y];
}
for (auto d : divisor[a[x]])
ans[x] += u[d]*cnt[d];
ans[x] = size[x]-1-ans[x];
}
Note that ans[x] = ∑ u[d]*( (cnt[d] after dfs the subtree of x) - (cnt[d] before dfs the subtree of x) ), which implies that ( (cnt[d] after dfs the subtree of x) - (cnt[d] before dfs the subtree of x) ) is to calculate s(d).
Note that when we run dfs(x, pre), before looping “for (auto y : v[x])”, for each a[x]'s divisor d, what we do is “cnt[d] ++”. And the difference of cnt[d] before and after the loop is exactly what we want to calculate, i.e. s(d). If still confused, think of the DFS order of a tree and implement it by hand in order to understand what the procedure exactly does.
I did understand why you were subtracting first and adding up after the children were visited, because of the DFS order, but I guess I didn’t fully grasp what was happening. I thought about it a bit more and it’s clear to me now, thanks!