求助，D 题写的正解思路，样例过了，但是评测时全部超时

Kus 重构树 + 倍增LCA 不会超时吧 ，求助

#include 
#include 
#include 
//#define int unsigned long long 
//#define int long long
using namespace std;
const int B=5e5+10;
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;
}
pairmyRanq(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);
}
int n,m;
int q;
ull a1,a2;
int read() {int x;scanf("%d",&x);return x;}
namespace Seg
{
    struct node{int u,v,w;} e[B];
    int cmp(node a,node b) {return a.w<b.w;}
}
int fa[B];
int val[B];
int tot;
struct node{int v,nxt;} e[B<<1];
int head[B],cnt;
void modify(int u,int v)
{
    e[++cnt]=(node){v,head[u]};
    head[u]=cnt;
}
int find(int x) 
{
    if (fa[x]==x) return  x;
    else  return fa[x]=find(fa[x]);
}
int f[B][21],dep[B]; 
void dfs(int u,int pre)
{
    dep[u]=dep[pre]+1; 
    for (int i=1;(1<<i)<=dep[u];i++) f[u][i]=f[f[u][i-1]][i-1];
    for (int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if (v==pre) continue;
        f[v][0]=u;
        dfs(v,u);
//        if (i==0) break;
    } 
}
int Lca(int x,int y)
{
    if (dep[x]<dep[y]) swap(x,y);
    for (int i=20;i>=0;i--)
    { 
        if (dep[f[x][i]]>=dep[y]) 
            x=f[x][i];
    }
    if (x==y) return x;
    for (int i=20;i>=0;i--)
    {
        if (f[x][i]!=f[y][i]) 
        {
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}
int main()
{
    n=read(),m=read();
    for (int i=1;i<=2*n;i++) fa[i]=i;
    for (int i=1;i<=m;i++) {Seg::e[i]=(Seg::node){read(),read(),read()};}
    tot=n;    sort(Seg::e+1,Seg::e+1+m,Seg::cmp);
    for (int i=1;i<=m;i++)
    {
        int x1=find(Seg::e[i].u),x2=find(Seg::e[i].v);
        if (x1==x2) continue;
        val[++tot]=Seg::e[i].w;
        fa[x1]=tot;    fa[x2]=tot;
        modify(x1,tot); modify(x2,tot);
        modify(tot,x1); modify(tot,x2);
    }
    dfs(tot,0);
    q=read();
    scanf("%llu%llu",&a1,&a2);
    ull ans=0;
    while (q--)
    {
        pairp;
        p=myRanq(a1,a2,n);
        ans^=val[Lca(p.first,p.second)];
    }
//    Print(ans);
    printf("%llu",ans);
}