求助tarjan卡空间

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
int a[20000005];
stack<int> stk;
int son[20000005][2];
unsigned long long ans;
namespace GenHelper
{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_()
    {
    b=((z1<<6)^z1)>>13;
    z1=((z1&4294967294U)<<18)^b;
    b=((z2<<2)^z2)>>27;
    z2=((z2&4294967288U)<<2)^b;
    b=((z3<<13)^z3)>>21;
    z3=((z3&4294967280U)<<7)^b;
    b=((z4<<3)^z4)>>12;
    z4=((z4&4294967168U)<<13)^b;
    return (z1^z2^z3^z4);
    }
}
void srand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}

struct node{
    int v,id;
}query[40000005];
int LCA[20000005];
int Nxt[20000005];
int Head[20000005];
bool vis[20000005];
int father[20000005];
int cnt,Cnt;
int edge[20000005];
int nxt[20000005];
int head[20000005];
void addedge(int u,int v){
    cnt++;
    edge[cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
    return;
}
void addquery(int u,int v,int id){
    Cnt++;
    query[Cnt]=node{v,id};
    Nxt[Cnt]=Head[u];
    Head[u]=Cnt;
    return;
}
int find(int x){
    if(father[x]==x)return x;
    return father[x]=find(father[x]);
}
void unionn(int x,int y){
    int fx=find(x),fy=find(y);
    if(fx==fy)return;
    father[fx]=fy;
    return;
}
void tarjan(int cur){
    vis[cur]=true;
    for(int i=head[cur];i;i=nxt[i]){
        int v=edge[i];
        if(!vis[v]){
            tarjan(v);
            unionn(v,cur);
        }
    }
    for(int i=Head[cur];i;i=Nxt[i]){
        node t=query[i];
        if(!vis[t.v])continue;
        LCA[t.id]=find(t.v);
    }
    return;
}

int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=n;i++){
        father[i]=i;
    }
    srand(s);
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    for(int i=1;i<=m;i++){
        int lt=read()%n+1,rt=read()%n+1;
        if(lt>rt)swap(lt,rt);
        addquery(lt,rt,i);
        addquery(rt,lt,i);
    }
    int rt=0;
    for(int i=1;i<=n;i++){
        int last=0;
        while(!stk.empty()&&a[stk.top()]<a[i]){
            last=stk.top();
            stk.pop();
        }
        if(!stk.empty()){
            son[stk.top()][1]=i;
        }
        else{
            rt=i;
        }
        son[i][0]=last;
        stk.push(i);
    }
    for(int i=1;i<=n;i++){
        if(son[i][0])addedge(i,son[i][0]),addedge(son[i][0],i);
        if(son[i][1])addedge(i,son[i][1]),addedge(son[i][1],i);
    }
    tarjan(rt);
    for(int i=1;i<=m;i++){
        ans+=a[LCA[i]];
    }
    printf("%llu",ans);
    return 0;
}
/*
一个数组76M 
*/

50分，完全不知道怎么卡。

维克托全寄了