Se nos da un gráfico G (V, E) con N nodos (numerados de 0 a N-1) y exactamente (N-1)bordes de dos vías.

Cada borde en una gráfica tiene unacosto positivo C (u, v)(Peso del borde).

La gráfica completa es tal queHay un camino único entre cualquier par de nodos..

También nos dan una listaL del número de nodo, en el que se colocan las bombas.

Nuestro objetivo esdañar / quitar el borde de la gráfica tal, que después de dañar / remover los bordes de la gráfica, no hay conexión entre las Bombas -

es decirDespués de dañar, no hay camino entre dos bombas..

loscosto de dañar el Edge (u, v) = Peso del borde (u, v).

Asi que,Tenemos que dañar esos bordes, de modo que el costo total de daño sea mínimo.

Ejemplo:

Total Nodes=N=5 
Total Bomb=Size of List L=3

List L={2,4,0}//Thats is at node number 2,4 and 0 bomb is placed...

Total Edges =N-1=4 edges are::

u v Edge-Weight

2 1 8

1 0 5

2 4 5

1 3 4



In this case the answer is ::
Total Damaging cost =(Edge Weight (2,4) + Edge Weight(0,1))
           =5+5=10.

So when we remove the edge connecting node (2,4),
and the edge connecting node (0,1) ,there is no connection left 
between any pair of machines in List {2,4,0};

Note any other,combinations of edges(that  we damaged ) to achieve the
target goal ,needs more than 10 unit cost.  

Constraints::
N(ie. Number of Nodes) <= 100,000
ListSize |L|(ie. Number of Bombs) <= N
1 <=Edge cost(u,v) <= 1000,000

¿Qué había hecho?

Hasta ahora, no había encontrado ninguna forma eficiente :(.

Además, como el número de nodos esN, el número de aristas es exactamenteN-1 y todo el gráfico es tal que hay una ruta única entre cualquier par de nodos, llegué a la conclusión de quela gráfica es unaÁRBOL.

Intenté modificar el algoritmo de Kruskal, pero eso tampoco me ayudó.

¡Gracias!