The spanning tree that possesses the properties described in the conditions for a good graph will be referred to as a “good spanning tree.” First, let’s consider how to determine the existence of a good spanning tree for a fixed graph.

If a good spanning tree exists, when we define the cost of an edge \((u,v)\) as \(|X_u - X_v|\) using a strictly increasing sequence \(X\), the good spanning tree will be one of the minimum spanning trees. This follows from the Kruskal’s algorithm and the fact that for an edge \((u,v)\) not included in the good spanning tree, the cost of the edges on the simple path connecting \(u\) and \(v\) will be less than \(|X_u - X_v|\).

Specifically, if we consider setting \(X_u = 10^u\) or \(-10^{N-u}\), the costs of each edge will be distinct, so the minimum spanning tree will be uniquely determined. The good spanning tree will be equal to both of the following:

• The minimum spanning tree \(T_1\) when the cost of edge \((u,v)\) is \((N+1)v - u\)
• The minimum spanning tree \(T_2\) when the cost of edge \((u,v)\) is \((N+1)(N+1-u) - (N+1-v)\)

Therefore, for a good spanning tree to exist, it is necessary that \(T_1 = T_2\).

Conversely,

• In \(T_1\), for an edge \((u,v)\), the maximum vertex number on the simple path connecting \(u\) and \(v\) must be \(v\).
• In \(T_2\), for an edge \((u,v)\), the minimum vertex number on the simple path connecting \(u\) and \(v\) must be \(u\).

Thus, the above conditions are also sufficient.

From the above, the existence of a good spanning tree can be determined by finding \(T_1\) and \(T_2\) and checking if they are identical.

Then, to determine the existence of a good spanning tree when each edge is removed, we can find the changes in the minimum spanning tree when the edge is removed and check for identicalness.

For the minimum spanning tree \(T\) of graph \(G\), the minimum spanning tree \(T_{u,v}\) of the graph obtained by removing edge \((u,v)\) can be obtained by the following steps:

• If \((u,v)\) is not included in \(T\), then \(T_{u,v} = T\). Otherwise, remove \((u,v)\) from \(T\). As a result, \(T\) will be divided into two connected components. Among the edges that span the two connected components, add the one with the minimum cost to \(T\) to obtain the tree \(T_{u,v}\).

Therefore, we need to solve the following problem:

For each edge $e$ in the minimum spanning tree $T$ of graph $G$, initialize a variable $X_e$ to $\infty$. For each edge $(u,v)$ in graph $G$ that is not included in $T$, update $X_e \leftarrow \min(X_e, C_{u,v})$ (where $C_{u,v}$ is the cost of edge $(u,v)$) for each edge $e$ included in the simple path connecting $u$ and $v$ in $T$, and find the final values of $X_e$.

This can be processed in \(O(M \log N)\) time by handling range chmin queries with a segment tree while performing a DFS. Alternatively, by decomposing the tree into heavy and light paths and arranging the heavy paths, it can be converted into \(O(\log N)\) range chmin queries, allowing it to be processed in \(O(M \log^2 N)\) time, which is also sufficient.