CF1528A Parsa's Humongous Tree

Parsa has a humongous tree on $ n $ vertices. On each vertex $ v $ he has written two integers $ l_v $ and $ r_v $ . To make Parsa's tree look even more majestic, Nima wants to assign a number $ a_v $ ( $ l_v \le a_v \le r_v $ ) to each vertex $ v $ such that the beauty of Parsa's tree is maximized. Nima's sense of the beauty is rather bizarre. He defines the beauty of the tree as the sum of $ |a_u - a_v| $ over all edges $ (u, v) $ of the tree. Since Parsa's tree is too large, Nima can't maximize its beauty on his own. Your task is to find the maximum possible beauty for Parsa's tree.

N/A

N/A

The trees in the example: In the first test case, one possible assignment is $ a = \{1, 8\} $ which results in $ |1 - 8| = 7 $ . In the second test case, one of the possible assignments is $ a = \{1, 5, 9\} $ which results in a beauty of $ |1 - 5| + |5 - 9| = 8 $