牛牛的无向图

链接：https://ac.nowcoder.com/acm/contest/7079/C
题解：
可以和旅游那道题一起分类到最小生成树里面，都是基于最小生成树的思想
d(u,v)定义为无向图中点 u 能到达点 v 的所有路径中权值最小的路径的权值。而路径的权值定义为为路径中权值最大值。
L按从小到大排序，如果当前L满足，那么集合当中两两之间都满足。
代码：

#include <bits/stdc++.h>
#define fastcall __attribute__((optimize("-O3")))
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define SZ(x) ((int)(x).size())
#define pb push_back
#define pii pair<int, int>
#define mset(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const int N = 5e5+10;
const double eps = 1e-11;

int u[N],v[N],w[N],L[N], r[N], p[N], si[N];
unsigned int SA, SB, SC; int n, m, q, LIM;
unsigned int rng61(){
    SA ^= SA << 16;
    SA ^= SA >> 5;
    SA ^= SA << 1;
    unsigned int t = SA;
    SA = SB;
    SB = SC;
    SC ^= t ^ SA;
    return SC;
}

void gen(){
    scanf("%d%d%d%u%u%u%d", &n, &m, &q, &SA, &SB, &SC, &LIM);
    for(int i = 1; i <= m; i++){
        u[i] = rng61() % n + 1;
        v[i] = rng61() % n + 1;
        w[i] = rng61() % LIM;
    }
    for(int i = 1; i <= q; i++){
        L[i] = rng61() % LIM;
    }
}

bool cmp(const int i, const int j){return w[i] < w[j];}
int find(int x){return p[x] == x ? x : p[x] = find(p[x]);}
int main()
{
    gen();
    ll ans = 0;
    sort(L+1, L+q+1);
    for(int i=1; i<=n; i++) p[i] = i;
    for(int i=1; i<=n; i++) si[i] = 1;
    for(int i=1; i<=m; i++) r[i] = i;
    sort(r+1, r+m+1, cmp);
    ll tmp = 0, i = 1;
    for(int k=1; k<=q; k++){
        for(; i<=m; i++){
            int e = r[i]; int x = find(u[e]); int y = find(v[e]);
            if(w[e] > L[k]) break;
            if(x == y) continue;
            else
            {
                tmp -= 1LL*si[x]*(si[x]-1)/2;
                tmp -= 1LL*si[y]*(si[y]-1)/2;
                p[x] = y;
                si[y] += si[x];
                tmp += 1LL*si[y]*(si[y]-1)/2;
            }
        }
        ans ^= tmp;
    }
    print(ans);
}