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?

Any kind of optimization suggestion would be helpful…

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?

Any kind of optimization suggestion would be helpful…

To Optimize…

- Use Lowest Common Ancestor method to Find shortest path between 2 nodes…
- Learn LCA from here Lowest Common Ancestor - Binary Lifting - Algorithms for Competitive Programming
- Also In each node store the sum from root node till that node…
- Create an array Sumat[] that stores the sum of all node values from root node to Present node…

According to LCA … lets say (

nodeu &nodev) 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.