Beautiful tree - ReimuOJ: Reimu Online Judge

Given a tree of

$n$ vertices. On vertex

$i$ , you can choose a number

$a_i$ that

$l_i \le a_i \le r_i$ and write on it. The beauty of the tree is defined as the sum of

$|a_u-a_v|$ for every edge

$(u, v)$ . Find the maximum possible beauty of the tree. ### Input - The first line contains an integer

$n$ . - The next

$n$ lines, each line contains 2 integers

$l_i, r_i$ . - The next

$n - 1$ lines, each line contains 2 integers

$u, v$ , there is an edge between

$u$ and

$v$ . ### Output - Print the maximum beauty of the tree. ### Constraints -

$1 \le n \le 10^5$ . -

$1 \le l_i \le r_i \le 10^9$ . -

$1 \le u, v \le n$ . ### Example Input:

$3 1 3 4 6 7 9 1 2 2 3$

Output:

$8$

Topic

Graph

Tree

Dynamic Programming

Rating

1500

Source

Codeforces

Solution (0)

Solution