Below \(E\) denotes the edge set of \(G\), and \((u,v,w)\) denotes an undirected edge connecting Vertices \(u\) and \(v\) of weight \(w\).

First, we explain how to solve the problem for each query. The minimum spanning tree \(T_i\) of \(G_i\) can be obtained in an \(O(N \log N)\) time by Kruskal’s algorithm described below.

First, prepare a UnionFind of \(N\) vertices.
Sort \(E \cap {e_i}\) by the weight of edges and inspect the edges in the increasing order of the weights. When inspecting Edge \((u,v,w)\),

• if Vertices \(u\) and \(v\) are connected in the UnionFind, do nothing;
  
• - if Vertices \(u\) and \(v\) are not connected in the Union Find, we decide to use this edge. Connect \(u\) and \(v\) in the UnionFind.
  

We repeat the operation until the entire graph becomes connected.

We can obtain \(T_i\) by the algorithm above, so we can obtain the answer for the problem by finding \(T_i\) for all queries, but the complexity will be \(O(Q \times N \log N)\), which is not efficient enough.

Taking a closer look at the operations above, we can observe that we may abort the algorithm once we inspect \(e_i\), as we only want to answer the query (determine whether \(T_i\) contains \(e_i\)). Specifically, we can process as follows. (The difference from the previous one is shown in bold text.)

First, prepare a UnionFind of \(N\) vertices.
Sort \(E \cap {e_i}\) by the weight of edges and inspect the edges in the increasing order of the weights. When inspecting Edge \((u,v,w)\),

1. If the edge currently inspected is \(e_i\),
   • If Vertices \(u\) and \(v\) are unconnected, output Yes, and otherwise output No, and abort the operations.
2. If the edge currently inspected is that of \(G\),
   • if Vertices \(u\) and \(v\) are connected in the UnionFind, do nothing;
     

• - if Vertices \(u\) and \(v\) are not connected in the Union Find, we decide to use this edge. Connect \(u\) and \(v\) in the UnionFind.
  

We could device a little improvement, but the complexity is still \(O(Q \times N \log N)\).

Taking a close look at the operation above, we can observe that only the edges of \(G\) affect the UnionFind data structure, but \(e_i\) does not.
Thus, the algorithm above can be parallelized; i.e. all the query computations can be processed in parallel. Specifically, we can assure that the algorithm below obtains the same result as performing an \( O(N \log N)\) algorithm \(N\) times.

First, prepare a UnionFind of \(N\) vertices.
Sort \(E\) and all the edges appear in the queries, \(E \cap \lbrace e_1 + e_2 + \dots + e_Q \rbrace\), by the weight of edges and inspect the edges in the increasing order of the weights. When inspecting Edge \((u,v,w)\),

1. If the edge currently inspected is \(e_i\) \({(1 \leq i \leq Q)}\),
   • If Vertices \(u\) and \(v\) are unconnected, let the answer for Query \(I\) be Yes; otherwise let it be No.
2. If the edge currently inspected is that of \(G\),
   • if Vertices \(u\) and \(v\) are connected in the UnionFind, do nothing;
     

• - if Vertices \(u\) and \(v\) are not connected in the Union Find, we decide to use this edge. Connect \(u\) and \(v\) in the UnionFind.
  

The algorithm above works in a total of \(\mathrm{O}((N+Q) \log (N+Q))\) time, which is fast enough for this problem. The technique of finding the answer of all queries in parallel is frequently used in problems scoring \(500\) points or more, so remember when facing query-related problems.

The sample code in Python follows. In order to get accepted, you need to use a processing system PyPy3. The 3-rd through 71-st lines are from ac-library-python.

Advanced problem: when queries are not independent

Some of you may be wondering: what if the query affects the later queries? In other words, we consider the following problem.

• Query \(i\): add an edge \((u,v,w)\) to \(G\) and output if \((u,v,w)\) is used for the minimum spanning tree as Yes or No. The added edge will persist for the next and later queries. All weights of queries are pairwise distinct.

I suspect that this advanced problem cannot be solved only with primitive data structures like Union Find. (Someone says that it can be solved with divide-and-conquer without advanced data structures in a total of \(O(N \log^2 N)\), but I don’t really understand it.)

This problem can be solved with an advanced data structure called Link/Cut Tree. A Link/Cut Tree enables us to do the following operations in an amortized \(O(\log N)\) time.

• When Vertices \(u\) and \(v\) are not connected, add an edge between \(u-v\). (Link)
• When there is an edge between Vertices \(u\) and \(v\), remove the edge between \(u-v\). (Cut)
• When Vertices \(u\) and \(v\) are connected, find the maximum value of the values that vertices on the path between Vertices \(u\) and \(v\) store (the “maximum value” can actually be anything as long as it is a commutable monoid)

It is a relatively straightforward consequence that if these operations can be performed fast enough, each query can be processed in an amortized \(\mathrm{O}(\log N)\) time. (By the way, the original problem can be solved in a total of \(\mathrm{O}(Q \log N)\) with Link/Cut Tree too.)

It is 100% sure that Link/Cut Tree is used in an intended/unintended solution of AtCoder, so the knowledge is not required to enjoy AtCoder, but I have an impression that this technique is often available as an unintended solution of query problems in unofficial contests, so if you a writer of competitive programming contests, you may want to grasp the details.