动态最小生成树是一类要求给定图，对于图的边有删除，插入，修改边权操作，满足查询MST（Minimum Spanning Tree ）的问题。
在这里我们考虑修改边的操作，删除可以看成是将边权设成INF，插入可以看做是将一条INF的边边权赋值。
那么假设我们有q个询问，每个询问修改一条边的权值。
对于q个询问里修改的边，我们设这个边集为Q，全集为E，那么对于E-Q中的边，做一遍MST，MST中的边集设为G，那么对于E-Q-G中的边，不论询问怎么改变，这些边都不会在MST中，所以我们可以删除这些边，这时全集E不包括刚才删除的边，全集中的边的数量变成了n+q，n为MST中必要的边，q为询问中的边。之后将Q中的边的边权都赋值为-ING，这时做一遍MST，如果E-Q的边在MST中，这时代表就算修改的边最小时这些边也要选，也就是这些边是保证MST连通性的必要的边，这些边我们也没有必要考虑，因为必须要选，所以将这条边连接的两个点合并成一个点，可以用并查集维护。那么这些操作之后，我们将边的规模变成了q的，点的规模变成了q的。那么我求出来询问包括1-q的情况了，在剩下的这张图（规模变小了）上，将询问的范围变成1-q>>1和q<<1-q，再递归的做下去，因为询问的不断地变小，每次都会有更多的边被缩掉（在第二次做MST时可以缩掉的边），每次边的规模都变成了q/2^dep，这样一共会有log2q层，每层做MST是qlog2q的，那么总的时间复杂度就是q(log2q，我们递归的时候不用每次都排序，可以保存原来有序的边集，所以可以去掉一个log2q，这样时间复杂度就变成了qlog2q。
练习题，bzoj 2001 http://61.187.179.132/JudgeOnline/problem.php?id=2001
/************************************************************** Problem: 2001 User: BLADEVIL Language: Pascal Result: Accepted Time:14456 ms Memory:37024 kb ****************************************************************/ //By BLADEVIL type node =record cnt :longint; a,b :array[1..250000]of longint; end; var e :array[1..18] of node; fa :array[1..20000]of longint; x, y, data, tdata :array[0..50000]of longint; num, cha, ord, opt :array[0..50000]of longint; i , n, m, q :longint; ans :int64; procedure swap(var a,b:longint); var t :longint; begin t:=a; a:=b; b:=t; end; procedure qsort(left,right:longint); var i, j, bj :longint; begin i:=left; j:=right; bj:=data[ord[(i+j) shr 1]]; while i<=j do begin while data[ord[i]]<bj do inc(i); while data[ord[j]]>bj do dec(j); if i<=j then begin swap(ord[i],ord[j]); inc(i); dec(j); end; end; if j>left then qsort(left,j); if i<right then qsort(i,right); end; procedure work(dep,left,right:longint); var i, tm, tcnt :longint; tans :int64; function getfather(a:longint):longint; var tmp :longint; begin if fa[a]=a then exit(a); tmp:=a; while fa[tmp]<>tmp do tmp:=fa[tmp]; while fa[a]<>tmp do begin inc(e[dep].cnt); e[dep].a[e[dep].cnt]:=a; e[dep].b[e[dep].cnt]:=fa[a]; fa[a]:=tmp; a:=e[dep].b[e[dep].cnt]; end; exit(tmp); end; procedure combine(a,b:longint); begin a:=getfather(a); b:=getfather(b); inc(e[dep].cnt); e[dep].a[e[dep].cnt]:=a; e[dep].b[e[dep].cnt]:=fa[a]; fa[a]:=b; end; procedure recover(a:longint); begin while e[dep].cnt<>a do begin fa[e[dep].a[e[dep].cnt]]:=e[dep].b[e[dep].cnt]; dec(e[dep].cnt); end; end; begin tans:=ans; e[dep].cnt:=0; if left=right then begin data[num[left]]:=cha[left]; tdata[num[left]]:=cha[left]; qsort(1,m); for i:=1 to m do if getfather(x[ord[i]])<>getfather(y[ord[i]]) then begin combine(x[ord[i]],y[ord[i]]); ans:=ans+data[ord[i]]; end; writeln(ans); recover(0); ans:=tans; exit; end; tm:=m; for i:=left to right do data[num[i]]:=-maxlongint; qsort(1,m); opt[0]:=0; for i:=1 to m do if getfather(x[ord[i]])<>getfather(y[ord[i]]) then begin combine(x[ord[i]],y[ord[i]]); if data[ord[i]]<>-maxlongint then begin inc(opt[0]); opt[opt[0]]:=ord[i]; end; end; recover(0); for i:=1 to opt[0] do begin combine(x[opt[i]],y[opt[i]]); ans:=ans+data[opt[i]]; end; tcnt:=e[dep].cnt; for i:=left to right do data[num[i]]:=maxlongint; qsort(1,m); opt[0]:=0; for i:=1 to m do if getfather(x[ord[i]])<>getfather(y[ord[i]]) then combine(x[ord[i]],y[ord[i]]) else if data[ord[i]]<>maxlongint then begin inc(opt[0]); opt[opt[0]]:=i; end; for i:=opt[0] downto 1 do begin swap(ord[opt[i]],ord[m]); dec(m); end; recover(tcnt); for i:=left to right do data[num[i]]:=tdata[num[i]]; work(dep+1,left,(left+right) shr 1); work(dep+1,(left+right) shr 1 +1,right); m:=tm; ans:=tans; recover(0); end; begin readln(n,m,q); for i:=1 to n do fa[i]:=i; for i:=1 to m do begin readln(x[i],y[i],data[i]); tdata[i]:=data[i]; ord[i]:=i; end; for i:=1 to q do readln(num[i],cha[i]); work(1,1,q); end.