题解 | #都市的柏油路太硬#

【D.都市的柏油路太硬】克鲁斯卡尔重构树的板子题，直接套板子就行了。

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 2e5 + 5;  // 点
const int M = 5e5 + 5;  // 边
int n, m;               // 点,边

// ==========================================================================
// 题目定义的随机数
typedef unsigned long long ull;
ull myRand(ull &k1, ull &k2) {
    ull k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= (k3 << 23);
    k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return k2 + k4;
}
pair<int, int> myRanq(ull &k1, ull &k2, int MAXN) {
    int x = myRand(k1, k2) % MAXN + 1, y = myRand(k1, k2) % MAXN + 1;
    if (x > y)
        return make_pair(y, x);
    else
        return make_pair(x, y);
}
// ==========================================================================
namespace LCA {
int dep[N], dfn[N], n;
int st[N << 1][35], lg2[35];

struct Edge {
    int to, next;
} edge[N << 1];

int head[N], edge_cnt;

void init() {
    edge_cnt = 0;
    memset(head, -1, sizeof head);
}

void Insert(int u, int v) {  // 插入邻接表
    edge[++edge_cnt].to = v;
    edge[edge_cnt].next = head[u];
    head[u] = edge_cnt;
}

void dfs(int u, int fa) {
    dfn[u] = ++n;  // dfs序(欧拉序列,n'=2n-1)
    dep[u] = dep[fa] + 1;
    st[n][0] = u;
    for (int i = head[u]; ~i; i = edge[i].next) {
        int v = edge[i].to;
        if (v == fa) continue;
        dfs(v, u);
        st[++n][0] = u;
    }
}

void build(int root) {
    n = 0;
    dfs(root, 0);

    lg2[1] = 0;  // log_2
    for (int i = 2; i <= n; i++) lg2[i] = lg2[i >> 1] + 1;
    for (int j = 1; (1 << j) <= n; j++) {  // 初始化st表(Range min_dfn query)
        for (int i = 1; i + (1 << j) <= n + 1; i++) {
            if (dep[st[i][j - 1]] < dep[st[i + (1 << (j - 1))][j - 1]])
                st[i][j] = st[i][j - 1];
            else
                st[i][j] = st[i + (1 << (j - 1))][j - 1];
        }
    }
}

int query(int u, int v) {
    int lef = dfn[u], rig = dfn[v], t = lg2[abs(rig - lef) + 1];
    if (lef > rig) swap(lef, rig);
    if (dep[st[lef][t]] < dep[st[rig - (1 << t) + 1][t]])
        return st[lef][t];
    else
        return st[rig - (1 << t) + 1][t];
}
};  // namespace LCA
// ==========================================================================
namespace Ex_Kruskal {
struct Edge {
    int u, v;
    ll w;
    bool operator<(const Edge &b) const { return w < b.w; }
} edge[M];

ll fa[N], val[N];
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }

void init() {
    iota(fa, fa + N, 0);
    LCA::init();
}
void build(int m) {
    sort(edge, edge + m);
    for (int i = 0; i < m; i++) {
        int x = find(edge[i].u), y = find(edge[i].v);
        if (x != y) {
            val[++n] = edge[i].w;
            fa[x] = fa[y] = n;
            LCA::Insert(n, x);
            LCA::Insert(n, y);
        }
    }
    LCA::build(n);
}
int query(int u, int v) { return val[LCA::query(u, v)]; }

};  // namespace Ex_Kruskal

// ==========================================================================
// 快读
template <typename T>
inline void read(T &x) {
    T f = 1;
    x = 0;
    char ch = getchar();
    while (0 == isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (0 != isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
    x *= f;
}
// ==========================================================================

int main() {
    read(n), read(m);  // 读入点数和边数
    int maxn = n;

    Ex_Kruskal::init();  // 初始化Ex_Kruskal

    for (int i = 0; i < m; i++) {  // 读入边(带权值)
        read(Ex_Kruskal::edge[i].u);
        read(Ex_Kruskal::edge[i].v);
        read(Ex_Kruskal::edge[i].w);
    }

    Ex_Kruskal::build(m);  // 构建Ex_Kruskal,参数(边数)

    int q;
    read(q);
    ull ans = 0, k1, k2;
    scanf("%llu%llu", &k1, &k2);
    while (q--) {
        pair<int, int> opt = myRanq(k1, k2, maxn);
        int u = opt.first, v = opt.second;
        ans ^= Ex_Kruskal::query(u, v);  // 查询
    }
    printf("%llu", ans);
    return 0;
}