【NOIP模拟】从我背后出现

Description

给定n个点m条边的无向连通图，对于每条边求出强制选这条边后的最⼩⽣成树⼤⼩。

\(n\leq 10^5,m\leq 2*10^5\)

Input Format

第 1 行包含两个整数 n，m，表示点数和路径数。第 2~m+1 行每行三个整数 ui，vi，wi，表示有一条可以修的路连接 ui 和 vi ，费用为 wi ,wi ≤ 1e9。

Output Format

输出 m 行，每行一个整数，表示选择第i条路径的前提下的最小花费。

路径按输入的顺序编号为 1~m 。

Solution

原图构造最小生成树，对于一条边，如果他是最小生成树上的边，那么答案不变，

那如果不在上面，例如一条边u to v，

那么肯定是在原先树上u到v的路径上删去一条边，然后把这条边添加上去，可以发现删去的是最大的边

然后倍增预处理一下树上最大边即可

Code

#include <cstdio>

#include <algorithm>

#include <cmath>

#define N 100010

#define ll long long

using namespace std;

struct info{

	int fr,to,w,nex,id;

	friend bool operator < (info a,info b){

		return a.w<b.w;

	}

}ke[N*2],e[N*4];

int n,m,_log,tot,head[N*4],dep[N],f[N][20];

ll mx[N][20],Ans,Que[N*2];

bool used[N*2];

inline int read() {

	int x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch = getchar();}

	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch = getchar();}

	return x*f;

}

inline void Link(int u,int v,int w){

	e[++tot].to=v;

	e[tot].w=w;

	e[tot].nex=head[u];

	head[u]=tot;

}

void dfs(int u,int fa){

	for(int i=1;i<=_log;++i){

		f[u][i]=f[f[u][i-1]][i-1];

		mx[u][i]=max(mx[u][i-1],mx[f[u][i-1]][i-1]);

	}

	for(int i=head[u];i;i=e[i].nex){

		int v=e[i].to;

		if(v==fa) continue;

		dep[v]=dep[u]+1;

		mx[v][0]=e[i].w;

		f[v][0]=u;

		dfs(v,u);

	}

}

int fa[N];

int Find(int u){

	return (fa[u]==u)?u:fa[u]=Find(fa[u]);

}

inline void kruskal(){

	for(int i=1;i<=n;++i) fa[i]=i;

	sort(ke+1,ke+m+1);

	int cnt=0;

	for(int i=1;i<=m;++i){

		int px=Find(ke[i].fr),py=Find(ke[i].to);

		if(px!=py){

			fa[px]=py;

			used[i]=1;

			Link(ke[i].fr,ke[i].to,ke[i].w);

			Link(ke[i].to,ke[i].fr,ke[i].w);

			cnt++;

			Ans+=ke[i].w;

		}

		if(cnt==n-1) break;

	}

}

inline ll LCA(int u,int v){

	ll r=0;

	if(dep[u]>dep[v]) swap(u,v);

	int d=dep[v]-dep[u];

	for(int i=0;i<=_log;++i)if(d&(1<<i)) r=max(r,mx[v][i]),v=f[v][i];

	if(u==v) return r;

	for(int i=_log;i>=0;--i)

		if(f[u][i]!=f[v][i]) r=max(r,max(mx[u][i],mx[v][i])),u=f[u][i],v=f[v][i];

	return max(r,max(mx[v][0],mx[u][0]));

}

int main(){

	n=read(),m=read();

	_log=log(n)/log(2);

	for(int i=1;i<=m;++i)ke[i].fr=read(),ke[i].to=read(),ke[i].w=read(),ke[i].id=i;

	kruskal();

	dfs(1,0);

	for(int i=1;i<=m;++i)

		if(used[i]) Que[ke[i].id]=Ans;

		else Que[ke[i].id]=Ans-LCA(ke[i].fr,ke[i].to)+ke[i].w;

	for(int i=1;i<=m;++i)

		printf("%lld\n",Que[i]);

	return 0;

}

巴特西