Parsa's Humongous Tree

Explicación

Sin pérdida de generalidad, supongamos que ya calculamos los mejores valores de belleza para todos los vecinos del vértice $u$ .

Sea $\texttt{range}_u$ el que guarda $l_u$ y $r_u$ , y $\texttt{adj}_u$ el que guarda los valores de belleza de todos los vértices adyacentes a $u$ .

Por ejemplo, pondremos

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

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

Digamos que seleccionamos $7$ , lo que nos da una belleza de $|7-2| + |7-3| + |7-6| + |7-9| = 12$ . ¿Podemos hacerlo mejor que esto?

Intuitivamente, para cualquier $X$ que elijamos como valor de belleza de $u$ , si hay más elementos mayores que este $X$ , hacer $X$ lo más pequeño posible sería más óptimo (aumentando las diferencias de estos elementos) y viceversa. Nótese que en un caso donde el número de valores de belleza mayores es el mismo que el de valores de belleza menores, poner $X$ en el mínimo o el máximo nunca disminuye la respuesta. Mover $X$ siempre aumenta la distancia para el otro extremo de los valores de belleza.

Esta observación es todo lo que necesitamos. Como poner $u$ en $l_u$ o $r_u$ es siempre óptimo, lo manejaremos con DP.

Si $\texttt{dp}[i][j]$ guarda la suma máxima de valores de belleza en el subárbol enraizado en $i$ cuando el “tipo de belleza” de $i$ es $j$ . Como el vértice $i$ solo puede tomar dos valores, $j$ será igual a $0$ cuando el valor de belleza de $u$ es $l_u$ y $1$ cuando el valor de belleza de $u$ es $r_u$ .

Nuestras transiciones son:

\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}|)

Esto esencialmente significa:

Si $u$ tiene la belleza $l_u$ :

$\texttt{dp}_{u \space 0} \mathrel{+}= \max($ belleza si $v$ tiene un valor de belleza de $l_v$ , belleza si $v$ tiene un valor de belleza de $r_v$ )

Si $u$ tiene la belleza $r_u$ :

$\texttt{dp}_{u \space 1} \mathrel{+}= \max($ belleza si $v$ tiene un valor de belleza de $l_v$ , belleza si $v$ tiene un valor de belleza de $r_v$ )

Implementación

Complejidad temporal: $\mathcal{O}(N)$

C++Java


#include <algorithm>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::pair;
using std::vector;
 
vector<vector<int>> adj;
vector<pair<int, int>> range;
vector<vector<long long>> dp;
 
// return optimal beauty value for vertex u with subtree v
long long mx_beauty(int u, int v, bool type) {
	if (!type) {
		long long swtch = dp[v][1] + abs(range[u].first - range[v].second);
		long long sm = dp[v][0] + abs(range[u].first - range[v].first);
 
		return std::max(swtch, sm);
	} else {
		long long swtch = dp[v][1] + abs(range[u].second - range[v].second);
		long long sm = dp[v][0] + abs(range[u].second - range[v].first);
 
		return std::max(swtch, sm);
	}
}
 
void calculate_dp(int u, int par) {
	for (int v : adj[u]) {
		if (v == par) { continue; }
 
		calculate_dp(v, u);
		dp[u][0] += mx_beauty(u, v, 0);
		dp[u][1] += mx_beauty(u, v, 1);
	}
}
 
int main() {
	std::cin.tie(0)->sync_with_stdio(0);
 
	int test_num;
	std::cin >> test_num;
 
	for (int t = 0; t < test_num; t++) {
		int n;
		std::cin >> n;
 
		range.clear();
		adj.assign(n, {});
		dp.assign(n, vector<long long>(2, 0));
 
		for (int i = 0; i < n; i++) {
			int l;
			int r;
			std::cin >> l >> r;
 
			range.push_back(make_pair(l, r));
		}
 
		for (int i = 0; i < n - 1; i++) {
			int u;
			int v;
			std::cin >> u >> v;
 
			adj[--u].push_back(--v);
			adj[v].push_back(u);
		}
 
		calculate_dp(0, -1);
 
		cout << std::max(dp[0][0], dp[0][1]) << endl;
	}
}


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();
		int t = io.nextInt();
 
		for (int tc = 0; tc < t; tc++) {
			int n = io.nextInt();
 
			l = new int[n + 1];
			r = new int[n + 1];
			dp = new long[n + 1][2];
			adj.clear();
 
			for (int i = 1; i <= n; i++) {
				l[i] = io.nextInt();
				r[i] = io.nextInt();
			}
 
			for (int i = 0; i <= n; i++) { adj.add(new ArrayList<>()); }
 
			for (int i = 0; i < n - 1; i++) {
				int u = io.nextInt(), v = io.nextInt();
				adj.get(u).add(v);
				adj.get(v).add(u);
			}
 
			calculateDP(1, -1);
 
			io.println(Math.max(dp[1][0], dp[1][1]));
		}
 
		io.flush();
	}
 
	private static void calculateDP(int u, int par) {
		for (int v : adj.get(u)) {
			// Continue if `v` is `u`'s parent.
			if (v == par) { continue; }
 
			// Calculate the DP values for 'v'.
			calculateDP(v, u);
 
			// DP transitions for 'u'.
			dp[u][0] += maxBeauty(u, v, false);
			dp[u][1] += maxBeauty(u, v, true);
		}
	}
 
	// Return optimal beauty value for vertex u with subtree v.
	private static long maxBeauty(int u, int v, boolean type) {
		if (!type) {
			long swtch = dp[v][1] + Math.abs(l[u] - r[v]);
			long sm = dp[v][0] + Math.abs(l[u] - l[v]);
 
			return Math.max(swtch, sm);
		} else {
			long swtch = dp[v][1] + Math.abs(r[u] - r[v]);
			long sm = dp[v][0] + Math.abs(r[u] - l[v]);
 
			return Math.max(swtch, sm);
		}
	}
 
	// CodeSnip{Kattio}
}