题目思路挺巧妙的。
感觉应该可以数据结构一波，发现n很小可以搞搞事啊。然后又发现给了512mb，顿时萌生大力线段树记录的念头
一开始想的是记录节点的fa，然后发现搞不动啊??
但其实边肯定最多只有n-1条，那么就可以记录选择的边，然后用归并合并即可
没清空答案还wa可一次(lll￢ω￢)，浪费时间写暴力和拍(lll￢ω￢)
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; int m; struct edge { int x,y,d; }e[110000]; struct node { int l,r,lc,rc,as[110]; }tr[210000];int trlen; int n,fa[110]; int findfa(int x) { if(fa[x]==x)return x; fa[x]=findfa(fa[x]);return fa[x]; } void mergesort(int now,int lc,int rc) { for(int i=1;i<=n;i++)fa[i]=i; int Llim=min(n-1,tr[lc].r-tr[lc].l+1); int Rlim=min(n-1,tr[rc].r-tr[rc].l+1); int p=1,i=1,j=1; int fx,fy; while(i<=Llim&&j<=Rlim&&p<=n-1) { int Lid=tr[lc].as[i],Rid=tr[rc].as[j]; if(e[Lid].d<e[Rid].d) { fx=findfa(e[Lid].x);fy=findfa(e[Lid].y); if(fx!=fy) { fa[fx]=fy; tr[now].as[p++]=Lid; } i++; } else { fx=findfa(e[Rid].x);fy=findfa(e[Rid].y); if(fx!=fy) { fa[fx]=fy; tr[now].as[p++]=Rid; } j++; } } while(i<=Llim&&p<=n-1) { int id=tr[lc].as[i]; fx=findfa(e[id].x),fy=findfa(e[id].y); if(fx!=fy) { fa[fx]=fy; tr[now].as[p++]=id; } i++; } while(j<=Rlim&&p<=n-1) { int id=tr[rc].as[j]; fx=findfa(e[id].x),fy=findfa(e[id].y); if(fx!=fy) { fa[fx]=fy; tr[now].as[p++]=id; } j++; } } //-----------merge----------------------------- void bt(int l,int r) { int now=++trlen; tr[now].l=l;tr[now].r=r; tr[now].lc=tr[now].rc=-1; if(l==r)tr[now].as[1]=l; else { int mid=(l+r)/2; tr[now].lc=trlen+1;bt(l,mid); tr[now].rc=trlen+1;bt(mid+1,r); mergesort(now,tr[now].lc,tr[now].rc); } } void query(int now,int l,int r) { if(tr[now].l==l&&tr[now].r==r) { tr[trlen+2]=tr[trlen+1]; mergesort(trlen+1,trlen+2,now); tr[trlen+1].r=tr[now].r; return ; } int lc=tr[now].lc,rc=tr[now].rc; int mid=(tr[now].l+tr[now].r)/2; if(r<=mid) query(lc,l,r); else if(mid+1<=l)query(rc,l,r); else query(lc,l,mid), query(rc,mid+1,r); } int main() { freopen("data.in","r",stdin); freopen("1.out","w",stdout); int Q; scanf("%d%d%d",&n,&m,&Q); for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].d); trlen=0;bt(1,m); int l,r; while(Q--) { scanf("%d%d",&l,&r); tr[trlen+1].l=l;tr[trlen+1].r=l-1; memset(tr[trlen+1].as,0,sizeof(tr[trlen+1].as)); query(1,l,r); long long ans=0; for(int i=1;i<=min(n-1,r-l+1);i++) ans+=((long long)(e[tr[trlen+1].as[i]].d)); printf("%lld ",ans); } return 0; }