Dado un árbol ponderado que contiene N Nodes y dos Nodes u y v , la tarea es encontrar el recuento de Nodes que tienen un peso principal en el camino simple entre u y v (ambos inclusive) . Ejemplos: Aporte: u = 3, v = 5 Salida: 2 Explicación: El peso principal en la … Continue reading «Recuento de todos los Nodes de peso principal entre Nodes dados en el árbol dado»
Dado un árbol que consta de N Nodes, una array de bordes[][3] de tamaño N – 1 tal que para cada {X, Y, W} en los bordes[] existe un borde entre el Node X y el Node Y con un peso de W y dos Nodes u y v , la tarea es encontrar la … Continue reading «Maximice la suma de rutas desde LCA de los Nodes u y v a uno de esos Nodes»
Dado un árbol binario y 3 Nodes a, b y c, la tarea es encontrar un Node en el árbol tal que después de eliminar todo el borde conectado a ese Node, a, b y c estén en tres árboles diferentes. A continuación se muestra un árbol con Nodes de entrada como c, j y … Continue reading «Eliminar los bordes conectados a un Node de modo que los tres Nodes dados estén en árboles diferentes»
Requisitos previos : gráfico , árbol de expansión , conjunto disjunto (unión: búsqueda) . Un árbol de expansión mínimo (MST) T , para un gráfico G dado, abarca todos los vértices de un gráfico dado y tiene una suma de peso mínima de todos los bordes, de todos los árboles de expansión posibles. El segundo … Continue reading «Segundo mejor árbol de expansión mínimo»
Recomendamos encarecidamente consultar la publicación a continuación como requisito previo para esto. Descomposición ligera pesada | Conjunto 1 (Introducción) En la publicación anterior, discutimos la descomposición Heavy-light (HLD) con la ayuda del siguiente ejemplo. Supongamos que tenemos un árbol desequilibrado (no necesariamente un árbol binario) de n Nodes , y tenemos que realizar operaciones en el … Continue reading «Descomposición ligera pesada | Conjunto 2 (Implementación)»
Dado un árbol , y los pesos de todos los Nodes. Cada consulta contiene dos enteros u y v , la tarea es encontrar el peso mínimo y máximo en la ruta simple entre u y v (ambos inclusive). Ejemplos: Aporte: Consulta=[{1, 3}, {2, 4}, {3, 5}] Salida: -1 5 3 5 -2 5 Explicación: … Continue reading «Consulta para encontrar el peso máximo y mínimo entre dos Nodes en el árbol dado usando LCA.»
Requisitos previos: LCE (Conjunto 1) , LCE (Conjunto 2) , Array de sufijos (n Log Log n) , algoritmo de Kasai y árbol de segmentos El problema de la extensión común más larga (LCE) considera una string s y calcula, para cada par (L , R), la substring más larga de s que comienza tanto … Continue reading «Extensión común más larga / LCE | Conjunto 3 (Método del árbol de segmentos)»
Dado un árbol binario, la tarea es encontrar la distancia entre dos claves en un árbol binario, no se dan punteros principales. La distancia entre dos Nodes es el número mínimo de aristas que se deben atravesar para llegar a un Node desde otro. Este problema ya se discutió en una publicación anterior, pero utiliza tres … Continue reading «Consultas para encontrar la distancia entre dos Nodes de un árbol binario: método O (logn)»