题目链接：F. Drivers Dissatisfaction
题意：n个点，m条边，每条边有一个w,代表这条路的不满意度，每一条边我们可以花费c来使不满意读-1；然后问你有s,找到一棵生成树是满意度最小
题解：对于s,我们可以知道花费在c最小的边上价值最优，我们可以先求一颗最小生成树，然后枚举没有用到的边，把连接这两点的最长边去掉判段能否更新最小值
这里求树上两点的最短路经过的最大值，我们可以有lca,或者树链抛分都可以
#include<bits/stdc++.h> #include<set> #include<cstdio> #include<iomanip> #include<iostream> #include<string> #include<cstring> #include<algorithm> #define pb push_back #define ll long long #define fi first #define se second #define PI 3.14159265 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define eps 1e-7 #define pii pair<int,int> typedef unsigned long long ull; const int mod=1e3+5; const ll inf=0x3f3f3f3f3f3f3f; const int maxn=2e5+5; using namespace std; int n,m,w[maxn],c[maxn],f[maxn],dep[maxn],s,head[maxn],cnt; bool vis[maxn]; int fa[20][maxn],mx[20][maxn];//mx[i][x]保存x往上走2^i最长边的id struct data{ int u,v,w,c,id; bool operator<(const data b) { return w<b.w; } }da[maxn]; struct edge { int to,nxt,w,id; }e[maxn<<1]; int find(int x) { if(f[x]==x)return x; return f[x]=find(f[x]); } void link(int x,int y) { f[find(y)]=find(x); } void add_edge(int u,int v,int id) { e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;e[cnt].id=da[id].id;e[cnt].w=da[id].w; e[++cnt].to=u;e[cnt].nxt=head[v];head[v]=cnt;e[cnt].id=da[id].id;e[cnt].w=da[id].w; } void dfs(int v) { for(int i=1;i<20;i++) { fa[i][v]=fa[i-1][fa[i-1][v]]; if(w[mx[i-1][fa[i-1][v]]]<w[mx[i-1][v]])mx[i][v]=mx[i-1][v]; else mx[i][v]=mx[i-1][fa[i-1][v]]; } for(int i=head[v];i;i=e[i].nxt) { int to=e[i].to; if(to!=fa[0][v]) { dep[to]=dep[v]+1; fa[0][to]=v; mx[0][to]=e[i].id; dfs(to); } } } int lca(int x,int y) { if(dep[x]<dep[y])swap(x,y); int t=dep[x]-dep[y],temp=0,ans=0; for(int i=0;i<20;i++) { if(t>>i&1) { if(w[mx[i][x]]>temp)ans=mx[i][x],temp=w[mx[i][x]]; x=fa[i][x]; } } if(x==y)return ans; for(int i=19;i>=0;i--) { if(fa[i][x]!=fa[i][y]) { if(w[mx[i][x]]>temp)ans=mx[i][x],temp=w[ans]; if(w[mx[i][y]]>temp)ans=mx[i][y],temp=w[ans]; x=fa[i][x]; y=fa[i][y]; } } if(w[mx[0][x]]>temp)ans=mx[0][x],temp=w[ans]; if(w[mx[0][y]]>temp)ans=mx[0][y],temp=w[ans]; return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>n>>m; for(int i=1;i<=m;i++)cin>>w[i],da[i].w=w[i]; for(int i=1;i<=m;i++)cin>>c[i],da[i].c=c[i]; for(int i=1;i<=m;i++) cin>>da[i].u>>da[i].v,da[i].id=i; cin>>s; sort(da+1,da+1+m); for(int i=0;i<=n;i++)f[i]=i; ll ans=0,num=-1;int cn=n-1; for(int i=1;i<=m;i++) { if(find(da[i].v)!=find(da[i].u)) { vis[da[i].id]=true; link(da[i].v,da[i].u); add_edge(da[i].v,da[i].u,i); if(num==-1)num=da[i].id; else if(c[num]>da[i].c) num=da[i].id; ans+=da[i].w; if(--cn==0)break; } } ll sum=ans; ans=sum-s/c[num]; dfs(1); int del=0; for(int i=1;i<=m;i++) { if(!vis[da[i].id]) { int id=da[i].id; int t=lca(da[i].u,da[i].v); if(t==0)continue; ll tmp=sum-w[t]+w[id]-s/c[id]; if(tmp<ans) { del=t;num=da[i].id; ans=tmp; } } } if(del)vis[del]=false,vis[num]=true; cout<<ans<<endl; w[num]-=s/c[num]; for(int i=1;i<=m;i++) { if(vis[i]) { cout<<i<<" "<<w[i]<<endl; } } return 0; }