How to solve D?

My idea: So i was thinking we could have a map like structure to check existence of a particular sum like each node will also have a map where the mp[val] = i if there are i neighbours with value = val as an edge else 0(default).

Then I thought of just keeping a queue/stack where I just push {sum,node,vis}. So Now it looks for the sum in the node's map and if found puts in the stack {sum+nodeval, new node, new vis} and increases answer by 1 and decreases the value of mp[sum] by 1. I feel like this could work but I couldnt implement in time.

I feel like there should be a much neater way to solve this.

I couldnt solve it during the contest.

but this is what I was thinking: use w(a * b) = w(a) + w(b) — w(gcd(a, b)). sieving and saving the omega values before hand for upto 2*10^5. I found that 2*3*5*7*11*13*17*19 = 9699690 so all the values for numbers < 2*10^5 should be below 8. Which means 8c2 there are only 28 possible pairs so we pre-calculate w as well for all possible pairs

The only thing I was stuck at is how to add this w^k for all i,j i<j without n^2.