题意：给出一个图，每条边有权值和花费c，每次花费ｃ能使的权值-1。给出一个预算，求减完权值后的一个最小生成树。
思路：感谢CC大神
有这样一个结论：最佳方案里必定存在一种，预算全部花费全部分配在一条边上。证明显然，对于任意一组解，都可以在内部再分配预算使总费用更小或不变。
于是先求出原图的最小生成树，枚举每条边。
对于在生成树中的，判断使这条边减费是否更优。
不在生成树上的，找出树上从x[i]到y[i]的路径（唯一）上a[i]最大的边，判断删除那条边并加入减费后的(x[i],y[i])是否更优。
1 type yjs=record 2 a:longint; 3 s:int64; 4 end; 5 var f,q,g:array[1..210000,0..19]of longint; 6 head,vet,next,len,num,a,b,c,x,y,dep,fa,inq,ya,yb:array[1..500000]of longint; 7 hth,mst,s:int64; 8 tot,n,m,i,del,k,tx,ty:longint; 9 t:yjs; 10 11 procedure swap(var x,y:longint); 12 var t:longint; 13 begin 14 t:=x; x:=y; y:=t; 15 end; 16 17 procedure qsort(l,r:longint); 18 var i,j,mid:longint; 19 begin 20 i:=l; j:=r; mid:=a[(l+r)>>1]; 21 repeat 22 while mid>a[i] do inc(i); 23 while mid<a[j] do dec(j); 24 if i<=j then 25 begin 26 swap(a[i],a[j]); swap(b[i],b[j]); swap(c[i],c[j]); 27 swap(x[i],x[j]); swap(y[i],y[j]); 28 inc(i); dec(j); 29 end; 30 until i>j; 31 if l<j then qsort(l,j); 32 if i<r then qsort(i,r); 33 end; 34 35 procedure add(a,b,c,d:longint); 36 begin 37 inc(tot); 38 next[tot]:=head[a]; 39 vet[tot]:=b; 40 len[tot]:=c; 41 num[tot]:=d; 42 head[a]:=tot; 43 end; 44 45 function lca(x,y:longint):longint; 46 var i,d:longint; 47 begin 48 if dep[x]<dep[y] then swap(x,y); 49 d:=dep[x]-dep[y]; 50 for i:=0 to 19 do 51 if d and (1<<i)>0 then x:=q[x,i]; 52 for i:=19 downto 0 do 53 if q[x,i]<>q[y,i] then 54 begin 55 x:=q[x,i]; y:=q[y,i]; 56 end; 57 if x=y then exit(x); 58 exit(q[x,0]); 59 end; 60 61 function clac(x,y:longint):yjs; 62 var i,d:longint; 63 cc:yjs; 64 begin 65 if dep[x]<dep[y] then swap(x,y); 66 d:=dep[x]-dep[y]; 67 cc.a:=0; cc.s:=-maxlongint; 68 for i:=19 downto 0 do 69 if d and (1<<i)>0 then 70 begin 71 if f[x,i]>cc.s then 72 begin 73 cc.a:=g[x,i]; 74 cc.s:=f[x,i]; 75 end; 76 x:=q[x,i]; 77 end; 78 exit(cc); 79 end; 80 81 function ask(x,y:longint):yjs; 82 var t:longint; 83 t1,t2:yjs; 84 begin 85 t:=lca(x,y); 86 t1:=clac(x,t); 87 t2:=clac(y,t); 88 if t1.s>t2.s then exit(t1); 89 exit(t2); 90 end; 91 92 function find(k:longint):longint; 93 begin 94 if fa[k]<>k then fa[k]:=find(fa[k]); 95 find:=fa[k]; 96 end; 97 98 procedure dfs(u,pre:longint); 99 var e,v,i:longint; 100 begin 101 for i:=1 to 19 do 102 begin 103 if dep[u]<(1<<i) then break; 104 q[u,i]:=q[q[u,i-1],i-1]; 105 if f[u,i-1]<f[q[u,i-1],i-1] then 106 begin 107 f[u,i]:=f[q[u,i-1],i-1]; 108 g[u,i]:=g[q[u,i-1],i-1]; 109 end 110 else 111 begin 112 f[u,i]:=f[u,i-1]; 113 g[u,i]:=g[u,i-1]; 114 end; 115 end; 116 e:=head[u]; 117 while e<>0 do 118 begin 119 v:=vet[e]; 120 if v<>pre then 121 begin 122 dep[v]:=dep[u]+1; 123 f[v,0]:=len[e]; 124 q[v,0]:=u; 125 g[v,0]:=num[e]; 126 dfs(v,u); 127 end; 128 e:=next[e]; 129 end; 130 end; 131 132 begin 133 134 readln(n,m); 135 for i:=1 to m do read(a[i]); 136 for i:=1 to m do read(b[i]); 137 for i:=1 to m do c[i]:=i; 138 for i:=1 to m do readln(x[i],y[i]); 139 readln(s); 140 ya:=a; yb:=b; 141 qsort(1,m); 142 for i:=1 to n do fa[i]:=i; 143 for i:=1 to m do 144 begin 145 tx:=find(x[i]); ty:=find(y[i]); 146 if tx<>ty then 147 begin 148 fa[ty]:=tx; 149 hth:=hth+a[i]; 150 inq[c[i]]:=1; 151 add(x[i],y[i],a[i],c[i]); 152 add(y[i],x[i],a[i],c[i]); 153 end; 154 end; 155 dfs(1,-1); 156 mst:=hth; 157 for i:=1 to m do 158 if inq[c[i]]=1 then 159 begin 160 if mst-s div b[i]<hth then 161 begin 162 hth:=mst-s div b[i]; 163 k:=c[i]; 164 end; 165 end 166 else 167 begin 168 t:=ask(x[i],y[i]); 169 if mst-ya[t.a]+a[i]-s div b[i]<hth then 170 begin 171 hth:=mst-ya[t.a]+a[i]-s div b[i]; 172 k:=c[i]; 173 del:=t.a; 174 end; 175 end; 176 writeln(hth); 177 for i:=1 to m do 178 begin 179 if i=del then continue; 180 if i=k then begin writeln(i,' ',ya[i]-s div yb[i]); continue; end; 181 if inq[i]=1 then writeln(i,' ',ya[i]); 182 end; 183 184 end.