Parsa's Humongous Tree
Contest: Codeforces Round 722 (Div. 1)
Difficulty rating: 1600
Tags: dfs and similar, divide and conquer, dp, greedy, trees

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.

Input format:
The first line contains an integer $$$t$$$ $$$(1\le t\le 250)$$$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$(2\le n\le 10^5)$$$ — the number of vertices in Parsa's tree.

The $$$i$$$-th of the following $$$n$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ $$$(1 \le l_i \le r_i \le 10^9)$$$.

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ $$$(1 \le u , v \le n, u\neq v)$$$ meaning that there is an edge between the vertices $$$u$$$ and $$$v$$$ in Parsa's tree.

It is guaranteed that the given graph is a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case print the maximum possible beauty for Parsa's tree.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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$$$

Example input:
3
2
1 6
3 8
1 2
3
1 3
4 6
7 9
1 2
2 3
6
3 14
12 20
12 19
2 12
10 17
3 17
3 2
6 5
1 5
2 6
4 6

Example output:
7
8
62

Editorial:
The solution is based on the fact that an optimal assignment for $$$a$$$ exists such that for each vertex $$$v$$$, $$$a_v \in {l_v, r_v}$$$.
Proving this fact isn't hard, pick any assignment for $$$a$$$. Assume $$$v$$$ is a vertex in this assignment such that $$$a_v \notin {l_v, r_v}$$$.
Let $$$p$$$ be the number of vertices $$$u$$$ adjacent to $$$v$$$ such that $$$a_u > a_v$$$.
Let $$$q$$$ be the number of vertices $$$u$$$ adjacent to $$$v$$$ such that $$$a_u < a_v$$$.
Consider the following cases:
• $$$p > q$$$: In this case we can decrease $$$a_v$$$ to $$$l_v$$$ and get a better result.
• $$$p < q$$$: In this case we can increase $$$a_v$$$ to $$$r_v$$$ and get a better result.
• $$$p = q$$$: In this case changing $$$a_v$$$ to $$$l_v$$$ or $$$r_v$$$ will either increase or not change the beauty of the tree.
Based on this fact, we can use dynamic programming to find the answer.
Define $$$dp_{v,0}$$$ as the maximum beauty of $$$v$$$'s subtree if $$$a_v$$$ is equal to $$$l_v$$$.
Similarly, define $$$dp_{v,1}$$$ as the maximum beauty of $$$v$$$'s subtree if $$$a_v$$$ is equal to $$$r_v$$$.
$$$dp_{v,j}$$$ is calculated based on $$$v$$$'s children, for each of $$$v$$$'s children such as $$$u$$$, we add $$$u$$$'s contribution to $$$dp_{v,j}$$$.
The transitions are:
• $$$dp_{v,0} += max(dp_{u,0} + |l_v - l_u| , dp_{u,1} + |l_v - r_u|)$$$
• $$$dp_{v,1} += max(dp_{u,0} + |r_v - l_u| , dp_{u,1} + |r_v - r_u|)$$$
It's clear that the answer is equal to $$$max(dp_{v,0}, dp_{v,1})$$$.
complexity: $$$\mathcal{O}(n)$$$