T2 牛半仙的妹子图

考虑只有最小瓶颈生成树上的边才能产生贡献，而最小生成树就是一棵最小瓶颈生成树。在Kruscal求最小生成树时在并查集中加入bitset维护颜色，记录每条边加入后的颜色数并维护前缀和。查询时在排序过的边权数组上二分，类似分块的方法查询。

注意起点也有颜色。我怎么觉得是题意表述不清，为什么自己家里还有妹子

const int maxn(5e5+10),maxc(600+10);
int n,m,q,s,c[maxn],opt;
using ll = long long;
ll mod;

struct Edge {
    int u,v,w;
}e[maxn];

class UnionAndFindSet {
private:
    int fa[maxn],rank[maxn];
    std::bitset<maxc> b[maxn];
    int Find(const int &x) {
        return x == fa[x] ? x : fa[x] = Find(fa[x]) ;
    }
public:
    void Init() {
        for(int i(1);i<=n;i++) {
            fa[i]=i;rank[i]=1;b[i]=0ULL;b[i].set(c[i]);
        }
    }
    inline void Merge(const int &x,const int &y) {
        int u(Find(x)),v(Find(y));
        if(u==v) return;
        if(rank[u]<rank[v]) swap(u,v);
        fa[v]=u;rank[u]=max(rank[u],rank[v]+1);
        b[u]|=b[v];
    }
    inline bool Same(const int &u,const int &v) {
        return Find(u)==Find(v);
    }
    inline int Color(const int &u) {
        return b[Find(u)].count();
    }
}U;

int cnt;ll val[maxn],ans[maxn],sum[maxn];
void Kruscal() {
    std::sort(e+1,e+1+m,[](const Edge &p,const Edge &q) {
        return p.w<q.w;
    });
    U.Init();cnt=1;ans[1]=1;
    for(int i(1);i<=m&&cnt<n;i++) {
        if(U.Same(e[i].u,e[i].v)) continue;
        U.Merge(e[i].u,e[i].v);
        val[++cnt]=e[i].w;
        ans[cnt]=U.Color(s);
    }
    for(int i(1);i<cnt;i++)
        sum[i]=sum[i-1]+ans[i]*ll(val[i+1]-val[i]);
}

inline ll Query(const ll &l,const ll &r) {
    int p(std::upper_bound(val+1,val+cnt+1,l)-val-1); // 第一个小于等于l的
    int q(std::upper_bound(val+1,val+cnt+1,r)-val-1); // 第一个小于等于r的
    if(p==q) return (r-l+1)*ans[p];
    ll Ans(sum[q-1]-sum[p]);
    Ans+=(val[p+1]-l)*ans[p];
    Ans+=(r-val[q]+1)*ans[q];
    return Ans;
}

int main(void) {
    cin>>n>>m>>q>>s>>opt;
    if(opt) cin>>mod;
    for(int i(1);i<=n;i++) cin>>c[i];
    for(int i(1);i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
    Kruscal();ll last(0LL);
    for(int i(1);i<=q;i++) {
        ll l,r;cin>>l>>r;
        if(opt) {
            l=(l^last)%mod+1;
            r=(r^last)%mod+1;
        }
        if(l>r) swap(l,r);
        cout<<(last=Query(l,r))<<endl;
    }
    return 0;
}