Problem Link - https://www.codechef.com/problems/SJ1

~~My solution - https://www.codechef.com/viewsolution/24041293~~

**Updated Solution Without WA and 1 based indexing** - https://www.codechef.com/viewsolution/24048002

(Still not working)

I am not able to get why my solution is giving TLE for all cases except 2 cases.

I have commented the relevant part of my code.

My approach -

Storing graph as Adjacency List (Undirected). Storing v_i and m_i for each node in array p of Pair class where p[i].first represents v_i and p[i].second represents m_i.

I have traversed the using DFS from root by passing v_{root} and checked if the current node curr is leaf node or not.

For checking if it is leaf node I have checked if the size of adjacency list of curr node \leq 1.

If it is leaf node then I will calculate the g_{rl} = gcd (gcdtillnow, v_{curr})

where gcdtillnow was passed at every step of DFS.

Then again g_{m} = gcd(g_{rl}, m_{l_i}) and subtracting this value from m_{l_{i}}, then I have added this result with the leafno l_i in TreeMap. In c++ terms I think it is sorted_map.

If the curr node is not dfs then send the value gcd_{rc} = gcd(gcdtillnow, v_i)

Why I am getting TLE. Can anyone help me out.

If any clarification require in my explanation then please mention.

Thank You