So there is this question :
we are given a tree with n nodes. For each node, $i$ we are assigned two values : a $r_i$, that is the right boundary, and a $l_i$, which is the left boundary. We should give each node, $v_i$, a value , $a_i$, that $ a_i \in \lbrack l_i, r_i \rbrack$ . in other words $ l_i \le a_i \le r_i $. if edges are weighted and each weight of edges between every node $ (a_u, a_v)$ is equal to $ |a_v - a_u|$, then calculate the maximum possible sum of edges in this tree.
My idea to solve this question was to use a Dynamic Programming approach. I intuitively guessed that if we want to maximize the result, we should choose the boundary values for each $a_i$. Then I assumed that we need to create an $n \times 2 $ DP array. $dp[i][0]$ is the maximum subtree contribution if we assign $ a_i = l_i $ and $dp[i][1]$ is the maximum subtree contribution if we assign $ a_i = r_i $. Then I assumed that we start from the leaves of the tree to fill the table and this would be recurrence relations: $$ dp[leaf][0] = dp[leaf][1] = 0\\ \\ dp[i][0] = \sum_{c∈children(i)}{max(∣l_i−l_c∣+dp[c][0],∣l_i−r_c∣+dp[c][1])} \\ \\ dp[i][1] = \sum_{c∈children(i)}{max(∣r_i−l_c∣+dp[c][0],∣r_i−r_c∣+dp[c][1])} \\ \\ answer = max(dp[root][0], dp[root][1]) \\ $$ However, I can't think of a proof for this algorithm. I know that in Dynamic Programming algorithms we check for overlapping subproblems and optimal substructures, but cannot provide a reasonable proof for why we should choose the boundary values. I'd appreciate it if anyone could help me prove its correctness, or even if it's wrong, help me find the correct answer.
My closest attempt at proving : if we take a node $a_i$ and all the neighboring nodes of i, $\mathcal{N}(i) = \{a_{j_1}, a_{j_2}, ..., a_{j_k}\}$, then the sum of edges that this node is contributing to the total sum would be $ \sum_{j_t \in \mathcal{N}(i)}{|a_i - a_{j_t}|}$ which can be maximized only when $a_i$ is equal to $r_i$ or $l_i$. Because then $a_{j_t}$ can be in two positions with respects to the range $ \lbrack l_i, r_i \rbrack $ : A it can be outside the range, so then the farthest from it would be one of the boundaries; B it can be inside the range, so then because of the nature of the absolute value function, it should be one of the boundary points to maximize the sum.
