Official Editorial (C++)

Explanation

Without loss of generality, let's assume we've already computed the best beauty values for all of vertex $u$'s neighbors.

Let $\texttt{range}_u$ store $l_u$ and $r_u$ and $\texttt{adj}_u$ store the beauty values of all vertices adjacent to $u$.

For example, we'll set

$\texttt{range}_u = \{1, 10\}$

$\texttt{adj}_u = \{2, 3, 6, 9\}$

Let's say that we select $7$, which gives us a beauty of $|7-2| + |7-3| + |7-6| + |7-9| = 12$. Can we do better than this?

Intuitively, for any $X$ that we choose to be $u$'s beauty value, if there's more elements that are greater than this $X$, making $X$ as small as possible would be more optimal (increasing differences for these elements) and vice versa. Note that in a case where the number of greater beauty values is the same as the number of smaller beauty values, setting $X$ to the minimum or maximum will never decrease the answer. Moving $X$ will always increase the distance for the other end of the beauty values.

This observation is all we need. Since setting $u$ to $l_u$ or $r_u$ is always optimal, we'll handle this through DP.

If $\texttt{dp}[i][j]$ stores the maximum sum of beauty values at the subtree rooted at $i$ when $i$'s "beauty type" is $j$. Since vertex $i$ can only take two values, $j$ will be equal to $0$ when $u$'s beauty value is $l_u$ and $1$ when $u$'s beauty value is $r_u$.

Our transitions are:

$\texttt{dp}_{u \space 0} \mathrel{+}= \max(\texttt{dp}_{v \space 0} + |range_{u \space 0} - range_{v \space 0}|, \texttt{dp}_{v \space 1} + |range_{u \space 1} - range_{v \space 0}|)$

$\texttt{dp}_{u \space 1} \mathrel{+}= \max( \texttt{dp}_{v \space 1} + |range_{u \space 1} - range_{v \space 1}|, \texttt{dp}_{v \space 0} + |range_{u \space 0} - range_{v \space 1}|)$

This essentially means:

If $u$ has the beauty $l_u$:

$\texttt{dp}_{u \space 0} \mathrel{+}= \max($beauty if $v$ has a beauty value of $l_v$, beauty if $v$ has a beauty value of $r_v$)

If $u$ has the beauty $r_u$:

$\texttt{dp}_{u \space 1} \mathrel{+}= \max($beauty if $v$ has a beauty value of $l_v$, beauty if $v$ has a beauty value of $r_v$)

Implementation

Time Complexity: $\mathcal{O}(N)$

Copy
#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::pair;
using std::vector;

vector<vector<int>> adj;

Copy
import java.io.*;
import java.util.*;

public class ParsasHumongousTree {
	private static List<List<Integer>> adj = new ArrayList<>();
	private static int[] l, r;
	private static long[][] dp;

	public static void main(String[] args) {
		Kattio io = new Kattio();