Getting TLE ... How can I optimize?

I am stuck with a TLE on problem CCBTS05 … Plz Help how can i optimize the problem, or what is the better Alternative method to approach this question?

Here, This is My solution…

Any kind of optimization suggestion would be helpful…

To Optimize…

According to LCA … lets say (node u & node v) have a common parent P so the path sum from u--p--v would be
MinSum = Sumat( v ) + Sumat( u ) - 2*Sumat( P ) + Nodevalue( P )

  • You can Find LCA in O(nlogn) and Answer each query in O(1)
    Hence The overall complexity would be still O(nlogn) and thus no TLE should occur.