CF609E Minimum spanning tree for each edge
题目描述
给你 \(n\) 个点，\(m\) 条边，如果对于一个最小生成树中要求必须包括第 \(i (1 \le i \le m)\) 条边，那么最小生成树的权值总和最小是多少。
输入格式
第一行 \(n,m\) ，后面 \(m\) 行每行 \(u,v,w\) 代表一条边。
输出格式
\(m\) 行，第 \(i\) 行一个整数代表包括第 \(i\) 条边时的最小权值和。
首先考虑构建一颗最小生成树，如果在最小生成树上的边权值就是最小生成树的权值了，否则，如果我们加上这条边，就会在原来的树上形成一个环，我们想让这个图变回一棵树，就需要在环上去掉一条边，为了保证构成的树最小，所以要去掉这个环上边权最大的边，去掉的这个边肯定在原图最小生成树上，所以树链剖分维护最小生成树的最大边权就可以了。
Code.
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
struct node
{
int u,v,w,id;
bool operator < (const node &o) const {
return w < o.w;
}
} a[N];
struct Seg {int l,r,mx;} tr[N<<2]; ll ans[N],res;
int p[N],h[N],ne[N<<1],e[N<<1],w[N<<1],idx,n,m,dep[N],sz[N],son[N],val[N],id[N],cnt,top[N],fa[N],pl[N];
void add(int u,int v,int c) {ne[++idx]=h[u],e[idx]=v,w[idx]=c,h[u]=idx;}
int find(int x) {if(p[x] != x) p[x]=find(p[x]); return p[x];}
void dfs(int u,int father,int depth)
{
sz[u]=1; fa[u]=father; dep[u]=depth;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i]; if(j == father) continue ;
val[j]=w[i]; dfs(j,u,depth+1); sz[u]+=sz[j];
if(sz[son[u]] < sz[j]) son[u]=j;
}
}
void dfs2(int u,int t)
{
id[u]=++cnt; top[u]=t; pl[cnt]=val[u];
if(! son[u]) return ; dfs2(son[u],t);
for(int i=h[u];~i;i=ne[i])
{
int j=e[i]; if(j == fa[u] || j == son[u]) continue ;
dfs2(j,j);
}
}
void pushup(int u) {tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx);}
void build(int u,int l,int r)
{
tr[u].l=l; tr[u].r=r;
if(l == r) return tr[u].mx=pl[l],void();
int mid = l + r >> 1;
build(u<<1,l,mid); build(u<<1|1,mid+1,r);
pushup(u);
}
int query(int u,int l,int r)
{
if(l <= tr[u].l && tr[u].r <= r) return tr[u].mx;
int mid = tr[u].l + tr[u].r >> 1,res=0;
if(l <= mid) res=max(res,query(u<<1,l,r));
if(r > mid) res=max(res,query(u<<1|1,l,r));
return res;
}
int q_query(int u,int v)
{
int res=0;
while(top[u] != top[v])
{
if(dep[top[u]] < dep[top[v]]) swap(u,v);
res=max(res,query(1,id[top[u]],id[u])); u=fa[top[u]];
}
if(dep[u] < dep[v]) swap(u,v); res=max(res,query(1,id[v]+1,id[u]));
return res;
}
int main()
{
memset(h,-1,sizeof h); scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w),a[i].id=i;
for(int i=1;i<=n;i++) p[i]=i;
stable_sort(a+1,a+1+m);
for(int i=1;i<=m;i++)
{
int u=a[i].u,v=a[i].v; u=find(u); v=find(v); if(u == v) continue ;
p[u]=v; res+=a[i].w; add(a[i].u,a[i].v,a[i].w); add(a[i].v,a[i].u,a[i].w);
}
dfs(1,0,1); dfs2(1,1); build(1,1,n);
for(int i=1;i<=m;i++) ans[a[i].id]=res+a[i].w-q_query(a[i].u,a[i].v);
for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
return 0;
}