Skip to Content
CTRL K

Parade

Explicación

Queremos hallar un camino en el árbol con la máxima cantidad de aristas adyacentes que no forman parte del camino.

Cualquier camino simple en un árbol enraizado sigue una de dos formas generales:

  1. Solo sube hacia la raíz (desde el nodo más bajo hasta el más alto del camino).
  2. Sube hacia la raíz y luego baja de nuevo.

Como cada camino tiene un único nodo más alto, podemos comprobar para cada nodo vv cuáles son los mejores caminos para cada caso si vv es el nodo más alto de ese camino. Haremos esto con programación dinámica.

Sean dp1[v]dp_1[v] y dp2[v]dp_2[v] la cantidad máxima de aristas adyacentes para cada caso con vv como el nodo más alto. Si CC es el conjunto de hijos de vv, entonces valen las siguientes recurrencias:

  1. dp1[v]=max⁡u∈C(dp1[u])+(Degree of v)−2dp_1[v] = \max_{u \in C}(dp_1[u]) + (\text{Degree of }v) - 2
  2. dp2[v]=max⁡u≠w∈C(dp1[u]+dp1[w])+(Degree of v)−3dp_2[v] = \max_{u \neq w \in C}(dp_1[u] + dp_1[w]) + (\text{Degree of }v) - 3

Podemos calcular ambos valores de forma eficiente llevando la cuenta de los dos mejores valores de dp1[u]dp_1[u] mientras iteramos por CC.

Como el camino debe tener longitud no nula, también necesitamos restar 1 de la respuesta si el grafo es una estrella (es decir, un árbol con N−1N - 1 hojas).

Implementación

Complejidad temporal: O(N)\mathcal O(N)

#include <bits/stdc++.h>
using namespace std;
 
vector<int> graph[200001];
int dp[2][200001];
 
void dfs(int node = 1, int parent = 0) {
	int mx1 = 1, mx2 = 1;
	for (int i : graph[node])
		if (i != parent) {
			dfs(i, node);
			if (dp[0][i] >= mx1) {
				mx2 = mx1;
				mx1 = dp[0][i];
			} else mx2 = max(mx2, dp[0][i]);
		}
	dp[0][node] = mx1 + graph[node].size() - 2;
	dp[1][node] = mx1 + mx2 + graph[node].size() - 3;
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
 
	int leaves = 0;
	for (int i = 1; i <= n; i++)
		if (graph[i].size() == 1) leaves++;
 
	dfs();
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (graph[i].size() > 1) ans = max(ans, max(dp[1][i], dp[0][i]) + 1);
	}
	// Comprobamos si el grafo es una estrella para restar 1
	cout << ans - (leaves == n - 1);
	return 0;
}
Fundamentos