Este problema puede resolverse mediante la descomposición con mucha luz.
En primer lugar, aquí hay una introducción a la descomposición de luz pesada. La idea esencial para QTREE es mantener un árbol de segmentos para almacenar distancias a lo largo de todos los caminos pesados del árbol. De esa manera, la consulta y la actualización de los pesos máximos de borde a lo largo de rutas pesadas se pueden hacer en tiempo O (log N). La solución del problema se puede dividir en tres pasos:
1. Cálculo inicial:
- Cómo usar un algoritmo rápido para la detección y el seguimiento del objeto anómalo
- ¿Qué es el conocimiento estructurado?
- ¿Cuáles son algunos de los buenos libros sobre Algoritmos de aprendizaje automático de árbol de decisión?
- ¿Puedo hacer que un usuario de matriz ingrese su tamaño?
- ¿Qué tan importante es para el hombre en el medio saber la técnica de cifrado?
- Rootea el árbol en cualquier vértice. Encuentra los bordes pesados y los caminos pesados en el árbol usando un dfs
- Cree un árbol de segmentos para almacenar las longitudes máximas de borde para intervalos a lo largo de caminos pesados. Normalmente hago esto usando un segundo dfs
2. Consulta:
- Dados los vértices u y v, encuentre w = ancestro común más bajo (u, v) usando saltos de bordes pesados o almacenando el 2º padre para cada vértice (prefiero el último de alguna manera).
- maxedge (uv) = max (maxedge (uw), maxedge (vw)). Como w es un antepasado de u y v, se puede calcular maxedge (u / vw) utilizando la descomposición de luz intensa en O (log² N)
3. Actualización:
- Si uv es un borde ligero, solo actualice su peso
- Si uv es un borde pesado, actualice el árbol de segmentos correspondiente a su ruta.
El cálculo inicial se puede hacer en O (N log N). Cada consulta toma O (log² N) y la actualización toma O (log N). Por lo tanto, la complejidad de la solución es O (N log N + Q log² N).
