Maximizar Cantidad de Nodos Objetivos al Unir Árboles I

Existen dos árboles no dirigidos con n y m nodos, con etiquetas distintas en los rangos [0, n - 1] y [0, m - 1], respectivamente.

Se te dan dos arreglos de enteros 2D edges1 y edges2 de longitudes n - 1 y m - 1, respectivamente, donde edges1[i] = [ai, bi] indica que hay una arista entre los nodos aia_i y bib_i en el primer árbol y edges2[i]=[ui,vi]edges2[i] = [u_i, v_i] indica que hay una arista entre los nodos uiu_i y viv_i en el segundo árbol. También se te da un entero k.

El nodo u es objetivo para el nodo v si el número de aristas en la ruta desde u hasta v es menor o igual a k. Nota que un nodo siempre es objetivo para sí mismo.

Devuelve un arreglo de n enteros answer, donde answer[i] es el número máximo posible de nodos objetivo para el nodo i del primer árbol si tienes que conectar un nodo del primer árbol con otro nodo del segundo árbol.

Nota que las consultas son independientes entre sí. Es decir, para cada consulta eliminarás la arista añadida antes de proceder a la siguiente consulta.

Ejemplos

Ejemplo 1:

Input: edges1 = [[0,1],[0,2],[2,3],[2,4]], edges2 = [[0,1],[0,2],[0,3],[2,7],[1,4],[4,5],[4,6]], k = 2 Output: [9,7,9,8,8] Explicación: Para i = 0, conecta el nodo 0 del primer árbol al nodo 0 del segundo árbol. Para i = 1, conecta el nodo 1 del primer árbol al nodo 0 del segundo árbol. Para i = 2, conecta el nodo 2 del primer árbol al nodo 4 del segundo árbol. Para i = 3, conecta el nodo 3 del primer árbol al nodo 4 del segundo árbol. Para i = 4, conecta el nodo 4 del primer árbol al nodo 4 del segundo árbol.


Ejemplo 2:

Input: edges1 = [[0,1],[0,2],[0,3],[0,4]], edges2 = [[0,1],[1,2],[2,3]], k = 1 Output: [6,3,3,3,3] Explicación: Para cada i, conecta el nodo i del primer árbol con cualquier nodo del segundo árbol.

Soluciones

Python
from collections import deque

class Solution:
   def BFS(self, start, adj, k):
       q = deque()
       q.append((start, -1))
       count = 0

       while q and k >= 0:
           size = len(q)
           count += size
           for _ in range(size):
               u, parent = q.popleft()
               for v in adj[u]:
                   if v != parent:
                       q.append((v, u))
           k -= 1
       return count

   def maxTargetNodes(self, edges1, edges2, k):
       m = len(edges1) + 1
       n = len(edges2) + 1

       # Construir listas de adyacencia para el árbol 1
       adj1 = [[] for _ in range(m)]
       for u, v in edges1:
           adj1[u].append(v)
           adj1[v].append(u)

       # Construir listas de adyacencia para el árbol 2
       adj2 = [[] for _ in range(n)]
       for u, v in edges2:
           adj2[u].append(v)
           adj2[v].append(u)

       # Preprocesamiento: Encontrar el mejor nodo en el Árbol-2
       best = 0
       for i in range(n):
           connections = self.BFS(i, adj2, k - 1)
           best = max(best, connections)

       # Construir respuesta
       res = []
       for i in range(m):
           connections = self.BFS(i, adj1, k)
           res.append(connections + best)
       return res
BUSCARCtrl K