最小生成树变形，倍增。
每条边有权值$1$和权值$2$，要求构造最小生成树，有一条边可以选择权值$2$，其余边选择权值$1$。
先对权值$1$求最小生成树，然后枚举每一条边用权值$2$去替换树中的边即可。
寻找树上某条连权值最大的边，带修改的可以采用树链剖分；无修改的可以将树有根化，然后计算两点到公共祖先之间的权值最大的边，倍增预处理即可。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<ctime> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0); void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } template <class T> inline void read(T &x) { char c = getchar(); x = 0; while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } } int n,m; struct Edge { int u,v; long long w1,w2; int id; int flag; }e[200010]; long long S,MST; int f[200010],dep[200010]; vector<int>T[200010]; int to[200010][35]; long long mx[200010][35]; int idx[200010][35]; int Find(int x) { if(x!=f[x]) f[x]=Find(f[x]); return f[x]; } bool cmp(Edge a,Edge b) { return a.w1<b.w1; } bool cmp2(Edge a,Edge b) { return a.id<b.id; } void dfs(int fa,int x,int y,int eid) { f[x]=fa; dep[x]=y; if(x==1) { to[x][0]=-1; mx[x][0]=-1; idx[x][0]=-1; } else { to[x][0]=fa; mx[x][0]=e[eid].w1; idx[x][0]=eid; } for(int j=1;j<=30;j++) { if((1<<j)>dep[x]-1) { to[x][j]=-1; mx[x][j]=-1; idx[x][j]=-1; continue; } to[x][j]=to[to[x][j-1]][j-1]; if(mx[x][j-1]>=mx[to[x][j-1]][j-1]) { mx[x][j]=mx[x][j-1]; idx[x][j]=idx[x][j-1]; } else { mx[x][j]=mx[to[x][j-1]][j-1]; idx[x][j]=idx[to[x][j-1]][j-1]; } } for(int i=0;i<T[x].size();i++) { int id=T[x][i]; int v; if(e[id].u==x) v=e[id].v; else v=e[id].u; if(f[v]!=0) continue; dfs(x,v,y+1,id); } } int F(int a,int b) { if(dep[a]<dep[b]) swap(a,b); long long MX=0; int res; if(dep[a]!=dep[b]) { while(1) { int L=0,R=30,pos; while(L<=R) { int mid=(L+R)/2; if(to[a][mid]!=-1&&dep[to[a][mid]]>=dep[b]) L=mid+1,pos=mid; else R=mid-1; } if(mx[a][pos]>=MX) MX=mx[a][pos], res=idx[a][pos]; a=to[a][pos]; if(dep[a]==dep[b]) break; } } if(a==b) return res; while(1) { if(f[a]==f[b]) { if(mx[a][0]>=MX) MX=mx[a][0], res=idx[a][0]; if(mx[b][0]>=MX) MX=mx[b][0], res=idx[b][0]; break; } int L=0,R=30,pos; while(L<=R) { int mid=(L+R)/2; if(to[a][mid]!=to[b][mid]) L=mid+1,pos=mid; else R=mid-1; } if(mx[a][pos]>=MX) MX=mx[a][pos], res=idx[a][pos]; if(mx[b][pos]>=MX) MX=mx[b][pos], res=idx[b][pos]; a=to[a][pos]; b=to[b][pos]; } return res; } int main() { cin>>n>>m; for(int i=1;i<=m;i++) cin>>e[i].w1; for(int i=1;i<=m;i++) cin>>e[i].w2; for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v; cin>>S; for(int i=1;i<=m;i++) e[i].w2=e[i].w1-S/e[i].w2; for(int i=1;i<=m;i++) e[i].id=i,e[i].flag=0; sort(e+1,e+1+m,cmp); for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=m;i++) { int A=Find(e[i].u), B=Find(e[i].v); if(A==B) continue; f[A]=B; MST+=e[i].w1; e[i].flag=1; T[e[i].u].push_back(e[i].id); T[e[i].v].push_back(e[i].id); } sort(e+1,e+1+m,cmp2); memset(f,0,sizeof f); dfs(-1,1,1,-1); /* for(int i=1;i<=n;i++) { printf("%d -- fa:%d -- dep:%d ",i,f[i],dep[i]); } */ int U,V; long long now=MST; for(int i=1;i<=m;i++) { int eid = F(e[i].u,e[i].v); if(MST-e[eid].w1+e[i].w2<=now) { now=MST-e[eid].w1+e[i].w2; U=eid; V=i; } } e[U].flag=0; e[V].flag=2; printf("%lld ",now); for(int i=1;i<=m;i++) { if(e[i].flag==0) continue; if(e[i].flag==1) printf("%d %lld ",i,e[i].w1); if(e[i].flag==2) printf("%d %lld ",i,e[i].w2); } return 0; }