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 (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.