Las emociones de Teto#12449

Las emociones de Teto (Editorial)

Autor del problema:	Taras Derkach
Preparado por:	Taras Derkach
Editorial:	Taras Derkach

Solución

Fijemos el vértice $v$ que elegimos como vértice central.

Después de esto, se eliminan todos los vértices que están a distancia exactamente $2$ de $v$ .

Veamos qué componentes conexas quedan.

La primera componente siempre contiene el propio vértice $v$ y todos sus vecinos. Denotemos su suma como $ce n t e r_{v}$ center_v:

ce n t e r_{v} = a_{v} + u \in a d j_{v} \sum a_{u} .

center_v = a_v + \sum_{u \in adj_v} a_u.

Las demás componentes solo pueden aparecer detrás de los vértices que fueron eliminados.

Sea $u$ un vecino del vértice $v$ , y sea $x$ un vecino del vértice $u$ , donde $x \neq = v$ x \ne v.

Entonces el vértice $x$ está a distancia exactamente $2$ de $v$ , por lo que se elimina. Después de eliminar $x$ , pueden quedar componentes que están detrás de sus otros vecinos.

Es decir, necesitamos conocer rápidamente el siguiente valor:

si existe una arista $(x, y)$ , cuál es la suma de la componente que queda del lado del vértice $y$ si eliminamos esta arista.

Denotemos esta suma como $s i d e (x, y)$ side(x,y).

Si enraizamos el árbol en el vértice $1$ , entonces $s i d e (x, y)$ side(x,y) se puede calcular fácilmente usando sumas de subárboles:

si $y$ es hijo de $x$ , entonces $s i d e (x, y) = s u b t r e e_{y}$ side(x,y) = subtree_y;
en caso contrario, $s i d e (x, y) = t o t a l - s u b t r e e_{x}$ side(x,y) = total - subtree_x.

Para cada vértice $x$ , guardaremos los dos valores mínimos y los dos valores máximos entre todos los $s i d e (x, y)$ side(x,y) para todos los vecinos $y$ .

¿Por qué dos? Porque a veces necesitamos tomar el mejor valor, pero prohibir una dirección específica. Por ejemplo, cuando miramos un vértice eliminado $x$ , no podemos tomar la dirección de vuelta hacia $u$ , porque llegamos a $x$ desde allí.

Luego, para cada vértice $u$ , guardaremos las menores y mayores sumas de componentes que pueden aparecer después de eliminar uno de los vecinos $x$ del vértice $u$ .

En otras palabras, para cada vecino $x$ del vértice $u$ , tomamos la mejor componente detrás de $x$ , pero no en la dirección de vuelta hacia $u$ .

Después de esta preparación, la respuesta para un vértice central fijo $v$ se puede encontrar rápidamente.

Primero tenemos la componente con suma $ce n t e r_{v}$ center_v.

Luego, para cada vecino $u$ del vértice $v$ , tomamos la menor y la mayor componente posible entre los vértices que están detrás de $u$ . Al mismo tiempo, debemos prohibir la dirección de vuelta hacia $v$ .

Entre todas las componentes encontradas, buscamos la suma mínima y la suma máxima. El contraste para el vértice $v$ es igual a:

ma x S u m - min S u m .

maxSum - minSum.

La respuesta es el máximo de este valor entre todos los vértices $v$ .

Ejemplo

En el primer ejemplo, es óptimo elegir el vértice $v = 4$ v = 4.

Entonces el vértice $2$ está a distancia exactamente $2$ de él, por lo que se elimina.

Después de la eliminación, quedan dos componentes conexas:

${1}$ con suma $1$ ;
${3, 4, 5}$ \{3,4,5\} con suma $3 + 4 + 5 = 12$ 3 + 4 + 5 = 12.

Por lo tanto, el contraste es igual a:

12 - 1 = 11.

12 - 1 = 11.

Complejidad

Calculamos las sumas de subárboles una sola vez, y después para cada vértice recorremos sus vecinos.

Cada arista se procesa solo un número constante de veces.

Por lo tanto, la complejidad de la solución es $O (n)$ .