同是O(nlog^2n)怎么常数差距就这么大呢,,,

同是LCT  怎么我的和Po姐姐的常数差距就这么大呢

我绝对是脑子被驴踢了才写这个垃圾算法

//By SiriusRen#include 
     
      using namespace std;const int N=1000500;int n,m,q,xx,yy,zz,tim[N],cnt;int first[N],next[N],v[N],tot;int fa[N],maxx[N],ch[N][2],rev[N],Q[N],top,opersize;const int LIMIT=100000000;char in[LIMIT],*p=in;inline int getInt(){    register int res=0;    while (*p<'0'||*p>'9')*p++;    while (*p>='0'&&*p<='9')res=res*10+*p++-'0';    return res;}struct Road{    int from,to,wei;Road(){}    Road(int z,int t,int e){
   from=z,to=t,wei=e;};}road[N],node[N];void add(int x,int y){v[++tot]=y,next[tot]=first[x],first[x]=tot;}bool isroot(int q){
   return ch[fa[q]][0]!=q&&ch[fa[q]][1]!=q;}void push_up(int p){    maxx[p]=p;    if(node[maxx[ch[p][0]]].wei>node[maxx[p]].wei)maxx[p]=maxx[ch[p][0]];    if(node[maxx[ch[p][1]]].wei>node[maxx[p]].wei)maxx[p]=maxx[ch[p][1]];}void push_down(int p){rev[ch[p][0]]^=1,rev[ch[p][1]]^=1,rev[p]=0,swap(ch[p][0],ch[p][1]);}void rotate(int p){    int q=fa[p],y=fa[q],x=(ch[q][1]==p);    ch[q][x]=ch[p][!x],fa[ch[q][x]]=q;    ch[p][!x]=q,fa[p]=y;    if(!isroot(q)){        if(ch[y][1]==q)ch[y][1]=p;        if(ch[y][0]==q)ch[y][0]=p;    }fa[q]=p;push_up(q);}void splay(int x){    Q[++top]=x;    for(int i=x;!isroot(i);i=fa[i])Q[++top]=fa[i];    while(top){
   if(rev[Q[top]])push_down(Q[top]);top--;}    for(int y=fa[x];!isroot(x);rotate(x),y=fa[x])if(!isroot(y)){        if((ch[y][0]==x)^(ch[fa[y]][0]==y))rotate(x);        else rotate(y);    }push_up(x);}void access(int x){
   for(int t=0;x;t=x,x=fa[x])splay(x),ch[x][1]=t,push_up(x);}void makeroot(int x){access(x),splay(x),rev[x]^=1;}bool connected(int x,int y){
   while(fa[x])x=fa[x];while(fa[y])y=fa[y];return x==y;}void link(int x,int y){makeroot(x),fa[x]=y;}void split(int x,int y){makeroot(x),access(y),splay(y);}void cut(int x,int y){split(x,y),ch[y][0]=fa[x]=0;push_up(y);}void insert(int l,int r,int pos,int L,int R,int wei){    if(l>=L&&r<=R){add(pos,wei);return;}    int mid=(l+r)>>1,lson=pos<<1,rson=lson|1;    if(mid
      
       =R)insert(l,mid,lson,L,R,wei);    else insert(l,mid,lson,L,R,wei),insert(mid+1,r,rson,L,R,wei);}pair
       
        oper[N];void dfs(int l,int r,int pos,long long ans){    int bottom=opersize;    for(int i=first[pos];i;i=next[i]){        Road temp=node[v[i]];        if(temp.from==temp.to)continue;        if(connected(temp.from,temp.to)){            split(temp.from,temp.to);            int tmp=maxx[temp.to];            if(node[tmp].wei<=temp.wei)continue;            ans-=node[tmp].wei;            cut(tmp,node[tmp].from),cut(tmp,node[tmp].to);            oper[++opersize]=make_pair(0,tmp);        }        ans+=temp.wei;        link(v[i],temp.from),link(v[i],temp.to);        oper[++opersize]=make_pair(1,v[i]);    }    int mid=(l+r)>>1,lson=pos<<1,rson=lson|1;    if(l==r){
   if(mid)printf("%lld\n",ans);}    else dfs(l,mid,lson,ans),dfs(mid+1,r,rson,ans);    while(opersize>bottom){        pair
        
         jy=oper[opersize--];        if(!jy.first)link(jy.second,node[jy.second].from),link(jy.second,node[jy.second].to);        else cut(jy.second,node[jy.second].from),cut(jy.second,node[jy.second].to);    }}int main(){    fread(p,1,LIMIT,stdin);    n=getInt(),m=getInt(),q=getInt();    for(int i=1;i<=m;i++)xx=getInt(),yy=getInt(),zz=getInt(),road[i]=Road(xx,yy,zz);    for(int i=0;i<=n;i++)node[i].wei=-1;    for(int i=1;i<=q;i++){        xx=getInt(),zz=getInt(),        node[++cnt+n]=road[xx];        insert(0,q,1,tim[xx],i-1,cnt+n);        tim[xx]=i,road[xx].wei=zz;    }    for(int i=1;i<=m;i++)node[++cnt+n]=road[i],insert(0,q,1,tim[i],q,cnt+n);    dfs(0,q,1,0);}
        
       
      
     

就当我理论AC了吧,,,