Does anyone know how to approach this one?
You are given an undirected weighted graph $$$G$$$ that is not necessarily connected. In this weighted graph, there is a subset of nodes called highlighted nodes. It is guaranteed that the induced subgraph containing these highlighted nodes is connected.
You are also given $$$q$$$ queries. Each query consists of one integer that changes the status of the node corresponding to that integer. That is: if the node is highlighted, it becomes unhighlighted, and if it is unhighlighted, it becomes highlighted. After each query, it is guaranteed that the induced subgraph of highlighted nodes will always either be an empty graph or connected.
For each query, you must find the maximum length of a simple path having the following properties:
The path's length is at least $$$1$$$.
The first node in the simple path is a highlighted node.
There is only one highlighted node in the simple path.
For each query, print the answer on its own line. If there are no simple paths with these properties, print "N/A" (without the quotes) on its own line.
Input:
Each test begins with two integers $$$n,\,m$$$ $$$(1 \le n \le 10^5,\,1 \le m \le 2 \cdot 10^5)$$$: the number of nodes in $$$G$$$ and the number of edges in $$$G$$$ respectively.
The next $$$m$$$ lines contain three integers $$$u,\,v,\,w$$$ $$$(1 \le u \le n,\,1 \le v \le n,\,-1 \le w \le 10^9;\,w \ne 0)$$$, indicating that there is an edge with weight $$$w$$$ connecting $$$u$$$ and $$$v$$$. It is guaranteed that for every pair of vertices, there is at most $$$1$$$ edge connecting them. Furthermore, it is guaranteed that no self-loops exist.
The next line contains a single integer $$$h$$$: the number of highlighted nodes. On the line after that, $$$h$$$ integers follow $$$(1 \le h_i \le n)$$$ — the original highlighted nodes.
The next line contains a single integer $$$q$$$: the number of queries $$$(1 \le q \le 10^5)$$$. The next $$$q$$$ lines consist of a single integer $$$r$$$, which changes the status of node $$$r$$$. It is guaranteed that the induced subgraph containing the highlighted nodes is always either empty or connected.
Output:
For each query, print the length of the longest simple path with the properties above. If no such path exists, print "N/A" without the quotes.
If this is a real problem, I think you missed some critical info from the statement. In the current version this problem is a more general case of the longest path problem, which is NP-hard, and cannot be solved in polynomial time.
oh I see, thanks. does NP-hard mean that there is nothing better than brute force?