牛半仙的妹子图 题解

首先提出结论：此题进行最小生成树之后结果不变

靠着这个结论，我们显然可以在最小生成树上以 为根遍历，处理出到每个节点的最大边权，进而求出到每一种类型的节点最小的最大边权。
题意要求我们求从 到 中每一种最大边权可获得的类型总数，由于节点种类数较少，考虑对于每个节点最小所需的边权排序，然后按照每一种最大边权可以获得的节点分类，统计最后答案。

接着证明上述结论。考虑 Kruskal 算法中的贪心思想，假设前 条边都已考虑完毕，设第 条边连接 和 两个集合（树）,则当前如果有另外的边能够连接此二集合，肯定会边权更大，在 和 两个集合统计答案时答案不会更优。再者两个集合内已经被考虑到的边边权一定小于当前边，目前在两个集合之间统计答案时最大的边权一定是当前边。
至此，我们知道了 Kruskal 算法中每一步都满足本题的贪心性质，用该算法求解最小生成树正确。

AC code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,q,sx;
bool opt;
const int N=500003,C=603;
int c[N],M;
int h[N],to[2*N],nxt[2*N];
ll val[2*N];
int tot=1;
int f[N];
ll d[N];
inline ll read(){
    ll xx=0,f=1;
    char c;
    while (!isdigit(c=getchar())) if (c=='-') f=-f;
    do xx=(xx<<1)+(xx<<3)+(c^48);
    while (isdigit(c=getchar()));
    return xx;
}
struct edge{
    int u,v;
    ll w;
    bool operator <(const edge x)const{
        return w<x.w;
    }
}e[N];
int get(int x){
    if (x==f[x]) return x;
    return f[x]=get(f[x]);
}
void add(int u,int v,ll w){
    tot++;
    nxt[tot]=h[u];
    h[u]=tot;
    val[tot]=w;
    to[tot]=v;
}
void mst(){
    for (int i=1; i<=n; i++) f[i]=i;
    sort(e+1,e+m+1);
    for (int i=1; i<=m; i++){
        int u=e[i].u,v=e[i].v;
        ll w=e[i].w;
        if (get(u)==get(v)) continue;
        f[get(u)]=get(v);
        add(u,v,w);
        add(v,u,w);
    }
}
void calc(int cur,ll maxflow,int pre){
    d[c[cur]]=min(d[c[cur]],maxflow);
//    cout<<cur<<endl;
    for (int i=h[cur]; i; i=nxt[i]){
        int y=to[i];
        ll w=val[i];
        if (y==pre) continue;
        calc(y,max(w,maxflow),cur);
    }
}
ll query(int l,int r){
    int ls=upper_bound(d+1,d+C-2,l)-d-1;
    int rs=upper_bound(d+1,d+C-2,r)-d-1; //确定l与r的种类数
    if (ls==rs){
        return (ll)(r-l+1)*ls;
    }
    ll ans=0;
    ans+=(ll)(d[ls+1]-l)*ls;
    ans+=(ll)(r-d[rs]+1)*rs;
    for (int i=ls+1; i<rs; i++){ //以种类数分类统计答案，时间O(600)
        ans+=(ll)(d[i+1]-d[i])*i;
    }
    return ans;
}
int main(){
//    freopen("graph.in","r",stdin);
//    freopen("graph.ans","w",stdout); 
    n=read(); m=read(); q=read(); sx=read(); opt=read();
    if (opt) M=read();
    for (int i=1; i<=n; i++) c[i]=read();
    for (int i=1; i<=m; i++) e[i]=(edge){(int)read(),(int)read(),read()};
    memset(d,0x7f,sizeof(d));
    mst(); //Kruskal 最小生成树
    calc(sx,0,0); //树上O(n)统计
    sort(d+1,d+C-2);
    ll lans=0;
    for (int i=1; i<=q; i++){
        ll l=read(),r=read();
        if (opt) l=(l^lans)%M+1,r=(r^lans)%M+1;
        if (l>r) swap(l,r);
        lans=query(l,r);
        printf("%lld\n",lans); //考场上lld没打丢了30pts
    }
    return 0;
}