AtCoder ABC 040 D

June 23, 2020

D - 道路の老朽化対策について

クエリが与えられ、それぞれのクエリに対して、Union-Findで条件を満たす連結成分の個数を数える問題。クエリの先読みをするんだけど、別に与えられた順番で考える必要はなくて、都合のいい(今回で言うと、一番新しい年度をもつ)クエリから考えればいいという問題。

template<typename T>
struct UnionFind {
    i64 sz;

    vector<T> parent;
    vector<i64> rank;

    UnionFind(i64 n) : sz(n) {
        parent.assign(n, 0);
        REP(i, n) {
            parent[i] = i;
        }
        rank.assign(n, 1);
    }

    T find(T t) {
        if (parent[t] == t) return t;
        return parent[t] = find(parent[t]);
    }

    bool unite(T t1, T t2) {
        t1 = find(t1);
        t2 = find(t2);
        if (t1 == t2) return false;

        if (rank[t1] < rank[t2]) swap(t1, t2);
        parent[t2] = t1;
        rank[t1] += rank[t2];
        return true;
    }

    bool same(T t1, T t2) {
        return find(t1) == find(t2);
    }
};

#define MAX_N 100'000
using P = pair<i64, i64>;
using E = pair<i64, P>;

int main() {
    i64 N, M; cin >> N >> M;
    vector<E> edge(M);
    REP(i, M) {
        i64 u, v, y; cin >> u >> v >> y;
        u--, v--;
        edge[i] = {y, {u, v}};
    }
    sort(edge.rbegin(), edge.rend());

    i64 Q; cin >> Q;
    vector<tuple<i64, i64, i64>> query(Q);
    REP(i, Q) {
        i64 u, w; cin >> u >> w;
        u--;
        query[i] = make_tuple(w, u, i);
    }
    sort(query.rbegin(), query.rend());

    UnionFind<i64> uf(N);
    i64 ei = 0;
    vector<i64> ans(Q);
    REP(q, Q) {
        auto [w, u, i] = query[q];
        while (ei < M && edge[ei].first > w) {
            P p = edge[ei].second;
            uf.unite(p.first, p.second);
            ei++;
        }
        ans[i] = uf.rank[uf.find(u)];
    }

    REP(i, Q) cout << ans[i] << endl;
    return 0;
}