algorithm - representations - Contando rutas de suma cero en un árbol

minimum spanning tree algorithm (2)

Nos da un árbol con N (up to 100,000) nodos. Cada borde tiene un valor de +1 o -1 y los nodos se numeran de 1 a N ¿Cuántos pares desordenados (A, B) existen de tal manera que en el camino A -> X -> B , donde X ( X != A && X != B ) es algún vértice en el camino entre A y B , la suma de pesas de borde en el camino A -> X es 0 y la suma de los pesos de borde en el camino X -> B es 0 ?

De esto se deduce que solo nos importan las longitudes de ruta uniformes, o la suma de los pesos de borde no puede ser 0 . No podemos iterar en el potencial A y B , de lo contrario obtenemos una solución O(N^2) , que no se ejecutará en menos de 1 segundo. ¿Algún consejo sobre cómo resolverlo? El programa debería ejecutarse en menos de 1 segundo, por lo que una solución O(N) u O(N logN) funcionaría.

Editar: Sin embargo, si podemos calcular el número de buenas rutas comenzando desde cada nodo, podríamos resolver el problema. ¿Es posible calcular esto? Suena DP-ish para mí, pero no estoy seguro.

No sé si esto será útil, pero en todo caso, creo que podría usar esta propiedad: tome un par (A,B) para el que exista tal ruta. Entonces sabemos que la suma de los pesos de los bordes (que llamaré la distancia de los vértices finales) de la ruta A -> ... -> B := d(A,B) = 0 , porque

d(A,B) = d(A,X) + d(X,B) = 0 + 0 = 0

Como ha comentado, solo nos importan los caminos de igual longitud; esto sugiere que cuando realmente verificamos los pares, primero coloreamos el árbol en dos colores (ya que todos los árboles son bipartitos) lo cual se puede hacer con avidez en Θ (n), y solo consideramos pares de vértices dentro de cada grupo de colores. Por supuesto, esto no mejora la complejidad del número de pares que tendremos que considerar, ya que todavía tenemos (n / 2) * (n-1) / 2 vértices en cada color, y el término está en Θ (n ^ 2) donde n es el número de vértices.

Ahora como dijiste, puedes contar las rutas en Θ (n ^ 2) usando BFS y verificando todos los pares de vértices en cada grupo de colores. Aquí hay otro pensamiento que podría ayudarlo:

Digamos que tenemos dos vértices V y U para los cuales d(A,V) = d(A,U) . Tenemos dos casos:

A -> ... -> V = A -> ... -> U -> ... -> V , lo que significa U (WLOG) se encuentra en el camino único de A a V. Entonces tenemos
d(A,V) = d(A,U) + d(U,V) <=> d(A,V) = d(A,V) + d(U,V) <=> d(U,V) = 0

Entonces, si U y V se encuentran en el mismo camino y tienen una distancia igual a A, la distancia d(U,V) = 0 .
Los dos caminos se bifurcan en alguna parte; deja que el vértice donde los caminos se bifurcan sea K. Entonces tenemos
d(A,V) = d(A,K) + d(K,V) <=> d(K,V) = d(A,V) - d(A,K) y
d(A,U) = d(A,K) + d(K,U) <=> d(K,U) = d(A,U) - d(A,K) y
d(U,V) = d(K,U) + d(K,V) = d(A,U) + d(A,V) - 2*d(A,K) = 2*(d(A,U) - d(A,K)) = 2 * d(K,U)

Entonces, si U y V no se encuentran en el mismo camino, su distancia entre sí depende de la distancia que el vértice tiene a A y la distancia A tiene a K ; o, simplificado, solo en la distancia de cualquiera de los vértices a K De manera más general, el hecho de que d(A,U) = d(A,V) solo implica d(U,V) = 0 en el caso de que cualquier vértice se encuentre en el camino de A a la otra, entonces usted puede '' t realmente dice algo por distancias iguales si la última condición no es el caso.

Si algo de esto te ayudará, no lo sé. No pude encontrar la forma de lograr lo que pides en un tiempo subcuadratico, y supongo que no es posible; Para mí, el problema se siente lejanamente relacionado con todos los pares de caminos más cortos, que tienen complejidad de tiempo en O (n ^ 2) usando BFS para cada vértice como un vértice de inicio. Sin embargo, se trata más de una sensación difusa que cualquier cosa que se parezca vagamente a un argumento convincente.

Voy a desarrollar un algoritmo a continuación que comienza como O(N^2) . Con una pequeña observación podemos cambiar la complejidad a algo sustancialmente más pequeño. No estoy muy seguro de lo que será ( O(N) u O(NlnN) ), pero parece ser menor que O(N^2) .

En el árbol, elija un nodo hoja arbitrario x0 y cree una lista vacía L0 .
Siga el nodo de hoja en una rama. Si la lista no está vacía, agregue el valor de este peso de borde a cada término de la lista, esto registra la suma acumulada de los pesos de borde hasta el momento.
Agregue este peso de borde a la lista.
Si este nuevo nodo solo tiene 2 ramas, vaya al paso 2 recorriendo la única dirección nueva y actualizando L0 . Repita hasta que haya 3 o más ramas en el nuevo nodo.
Para cada rama (que no sea la dirección de donde venimos) inicie de forma recursiva en cada subárbol con el paso 1, excepto que en este subárbol marque este nodo como especial. Cuando la recursividad llega a este nodo, se fusionará (paso 5) y se detendrá.
Fusión: ahora tenemos un conjunto de listas L0, L1, L2, ... que deben fusionarse en L0 . Cada una de estas listas representa las diferentes rutas y sus respectivas sumas acumulativas. Para cada par en cada lista, agregue al contador, m la cantidad de veces que estas sumas son iguales a cero. Esto asocia una suma para cada ruta posible en el gráfico . Cree una nueva lista L0 que sea una concatenación del conjunto L0, L1, L2, ...

El algoritmo anterior funciona, pero dado que estamos realizando una suma para cada ruta de gráfico, el costo debe ser al menos O(N^2) .

El truco aquí es no contar todos los caminos . Si, en cambio, ordenamos las listas, determinando si dos listas ordenadas de tamaño k1,k2 tienen una suma fija c se puede hacer simplemente iterando a través de las listas, una hacia adelante una hacia atrás. Entonces el conteo se puede hacer para cada par de listas en operaciones k1+k2 , no en operaciones k1*k2 como antes. Fusionar las listas también es trivial y tiene la misma complejidad ya que ya están ordenadas.

Bonificación: el método anterior se extiende trivialmente para pesos de borde arbitrarios (no solo -1, 1 ) y una suma fija arbitraria (no solo cero).