题解：P14329 [JOI2022 预选赛 R2] 交易计划 / Trade Plan

fish_love_cat · 2026-06-26 14:00:30 · 题解

每个点有颜色，每次询问给定两个点，要求只保留和这两个点颜色相同的点，判断两个点是否连通。

连通性问题光速考虑并查集。

把边染上两个颜色，分别代表左右端点，如果一个边只有一个颜色那么不妨先缩点。

按照颜色对把边分类，那么显然一个询问就是把一类的边建上去。询问分类离线下来，同类直接暴力扫桶往并查集上加边一起处理掉就是 O(m) 的。

于是你只需要有一个很可爱的并查集板子就做完了。复杂度线性。

vector<pair<int,int>>vv;
map<pair<int,int>,vector<pair<int,int>>>mp;
map<pair<int,int>,vector<pair<int,pair<int,int>>>>q;
int c[N],ans[N];
int main(){
    udsu dsu;
    int n,m,k;
    cin>>n>>m>>k;
    while(m--){
        int u,v;
        cin>>u>>v;
        vv.push_back({u,v});
    }
    for(int i=1;i<=n;i++)
    cin>>c[i];
    for(pair<int,int>i:vv)
    if(c[i.first]==c[i.second])
    dsu.merge(i.first,i.second);
    else mp[{min(c[i.first],c[i.second]),max(c[i.first],c[i.second])}].push_back(i);
    cin>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        if(c[x]>c[y])swap(x,y);
        q[{c[x],c[y]}].push_back({i,{x,y}});
    }
    for(pair<pair<int,int>,vector<pair<int,pair<int,int>>>>i:q){
        int tp=0;
        for(pair<int,int>j:mp[i.first])
        dsu.merge(j.first,j.second),tp++;
        for(pair<int,pair<int,int>>j:i.second)
        ans[j.first]=dsu.is(j.second.first,j.second.second);
        dsu.undo(tp);
    }
    for(int i=1;i<=m;i++)
    cout<<ans[i]<<'\n';
    return 0;
}
// …开什么玩笑。
// 我可是活了五百年之久的大魔族啊。

// 阿乌拉。
// 在你面前的是，
// 活了上千年的魔法使啊。

// “自裁吧，阿乌拉。”