Official Analysis

Explanation

We can solve this using some MST intuition. In Kruskal's algorithm, we are to sort the edges by non-decreasing weight and unite vertices if they are not already in the same component. Here, we can check every query using this algorithm by processing each edge of each query offline.

As we consider edges from non-decreasing weight, we can keep track of a partially-built MST. An edge can only be in a MST if we processed all edges that have weights less than this edge, and we are able to unite the endpoints of the edge. This is because edges that have the same weight are arbitrary, so if we prioritize considering this edge then another MST with the same total weight is constructed.

We process all edges in non-decreasing weight, and for each query, unite the endpoint of all the edges that have this weight. If any edge does not satisfy the condition, the whole query fails.

Implementation

Time Complexity: $\mathcal{O}(q \log n + m + q)$

Copy
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e5 + 1;  // use indexing starting from 1
vector<int> edge_by_weight[MAXN];
// query_by_weight[weight][index of query] = {index of edges}
map<int, vector<int>> query_by_weight[MAXN];

struct DSU {
	vector<int> p, sz;