RMQ + kusal 重构树 有没有大佬解决一下
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int B=2e5+10;
int read() {int x;scanf("%d",&x);return x;}
int n,m,k;
struct node{int v,nxt;} e[B<<1];
int head[B<<1 ],cnt;
void modify(int u,int v)
{
e[++cnt]=(node){v,head[u]};
head[u]=cnt;
}
struct node_{int u,v,w;} E[B<<1];
int cmp(node_ a,node_ b) {return a.w<b.w;}
int fa[B];
int val[B];
int find(int x) {return fa[x]==x ? x : fa[x]=find(fa[x]);}
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);
}
int t,dfn[B],f[B][21],dep[B];
void dfs(int u,int pre)
{
dfn[u]=++t;f[t][0]=u;dep[u]=dep[pre]+1;
for (int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
if (v==pre) continue;
dfs(v,u);
f[++t][0]=u;
}
}
int logg[B];
void RMQ()
{
logg[0]=-1;
for (int i=1;i<=t;i++) logg[i]=logg[i>>1]+1;
for (int j=1;j<=20;j++)
for (int i=1;i+(1<<j)-1<=t;i++)
f[i][j]=dep[f[i][j-1]]<dep[f[i+(1<<(j-1))][j-1]]?f[i][j-1]:f[i+(1<<(j-1))][j-1];
}
int Lca(int x,int y)
{
if (dfn[x]>dfn[y]) swap(x,y);
x=dfn[x],y=dfn[y];//
int s=logg[y-x+1];
return dep[f[x][s]]<dep[f[y-(1<<s)+1][s]]?f[x][s]:f[y-(1<<s)+1][s];
}
int now;
int main()
{
n=read(),m=read();
for (int i=1;i<=2*n;i++) fa[i]=i;
for (int i=1;i<=m;i++) E[i]=(node_){read(),read(),read()};
sort(E+1,E+1+m,cmp);
now=n;
for (int i=1;i<=m;i++)
{
int x1=find(E[i].u),x2=find(E[i].v);
if (x1==x2) continue;
++now;
val[now]=E[i].w;
int s=now;
fa[x1]=s,fa[x2]=s;
modify(now,x1); modify(x1,now);
modify(now,x2); modify(x2,now);
}
dfs(now,0);
RMQ();
int q=read(); ull a1,a2;
scanf("%llu%llu",&a1,&a2);
ull ans=0;
while (q--)
{
pair<int,int>p;
p=myRanq(a1,a2,n);
ans^=val[Lca(p.first,p.second)];
}
printf("%llu",ans);
}