Reference blog :- https://threads-iiith.quora.com/Centroid-Decomposition-of-a-Tree

Once we have centroid decomposition of a tree we claim that a path between two nodes x and y can be decomposed into two paths- x to (x,y)'s LCA and y to the LCA. But in the centroid tree the path is not the same path as it was not in the original tree, as some new edges are formed and old edges are removed as part of the centroid tree construction. So, while solving problems using this tree how is it like that this fact of having some new edges and some old edges removed does not matter?

Can anyone of you please provide some better explanation of http://codeforces.net/contest/449/problem/D than the explanation given in the editorial (http://codeforces.net/blog/entry/13112). I am new to such stuff so I am not good at grasping the concepts as other smart people are.

As part of this quora post(http://www.quora.com/What-is-Knuths-optimization-in-dynamic-programming) a description of knuth optimization has been given. It has been mentioned that :- it can be proven that mid[l,r-1] <= mid[l,r] <= mid[l+1,r] — this means monotonicity of mid by l and r. Can anyone of you please help me regarding how to prove it?