Parsa's Humongous Tree (Codeforces 1529C)
Tags: 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: 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: For each test case print the maximum possible beauty for Parsa's tree.

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

Sample Inputs:
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

Sample Outputs:
7
8
62

Solution (Python):
import sys
input = sys.stdin.readline

def dfs(ls, vs, dp_l, dp_v, adj, node, parent):
    for child in adj[node]:
        if child != parent:
            dfs(ls, vs, dp_l, dp_v, adj, child, node)
    dp_l[parent] += max(dp_l[node] + abs(ls[parent] - ls[node]), dp_v[node] + abs(ls[parent] - vs[node]))
    dp_v[parent] += max(dp_l[node] + abs(vs[parent] - ls[node]), dp_v[node] + abs(vs[parent] - vs[node]))
    pass

def solve():
    n = int(input())
    ls = [0] * (n + 1)
    vs = [0] * (n + 1)
    dp_l = [0] * (n + 1)
    dp_v = [0] * (n + 1)
    for i in range(1, n + 1):
        (ls[i], vs[i]) = map(int, input().split())
    adj = [[] for _ in range(n + 1)]
    for _ in range(1, n):
        (u, v) = map(int, input().split())
        adj[u].append(v)
        adj[v].append(u)
    dfs(ls, vs, dp_l, dp_v, adj, 1, 0)
    print(max(dp_l[1], dp_v[1]))
    pass
for _ in range(int(input())):
    solve()

Solution (Python):
import sys
input = sys.stdin.readline

def dfs(u, p, dp0, dp1, adj, lB, rB):
    for v in adj[u]:
        if v != p:
            dfs(v, u, dp0, dp1, adj, lB, rB)
    dp0[p] += max(dp0[u] + abs(lB[p] - lB[u]), dp1[u] + abs(lB[p] - rB[u]))
    dp1[p] += max(dp0[u] + abs(rB[p] - lB[u]), dp1[u] + abs(rB[p] - rB[u]))

def solve():
    n = int(input())
    lB = [0 for x in range(n + 1)]
    rB = [0 for x in range(n + 1)]
    dp0 = [0 for x in range(n + 1)]
    dp1 = [0 for x in range(n + 1)]
    for i in range(1, n + 1):
        (lB[i], rB[i]) = map(int, input().split())
    adj = [[] for x in range(n + 1)]
    for k in range(n - 1):
        (u, v) = map(int, input().split())
        adj[u].append(v)
        adj[v].append(u)
    dfs(1, 0, dp0, dp1, adj, lB, rB)
    print(max(dp0[1], dp1[1]))
for _ in range(int(input())):
    solve()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(int(100000.0))

def dfs(node, parent):
    left_sum = 0
    right_sum = 0
    for child in graph[node]:
        if child == parent:
            continue
        (left_val, right_val) = dfs(child, node)
        left_sum += max(left_val + abs(L[child] - L[node]), right_val + abs(R[child] - L[node]))
        right_sum += max(left_val + abs(L[child] - R[node]), right_val + abs(R[child] - R[node]))
    return (left_sum, right_sum)

def solve():
    return max(dfs(1, 1))
test_cases = int(input())
for test_case in range(test_cases):
    N = int(input())
    graph = [[] for i in range(N + 1)]
    L = [0] * (N + 1)
    R = [0] * (N + 1)
    for i in range(1, N + 1):
        (L[i], R[i]) = map(int, input().split())
    for i in range(N - 1):
        (u, v) = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)
    print(solve())