题意很清楚，给定一张带权无向图，对于图上的每一条边，询问包括这一条边的生成树中边权权值之和最小的。

首先想到的方法是每次都先把要求的这条边加入最小生成树，然后跑一遍 Kruskal，但用膝盖想一下都知道这样肯定是会 T 飞的，所以我们可以直接在原来的最小生成树上进行修改，也就是说，把这一条边强行塞进最小生成树，由于这样很明显会形成一个环，所以我们还需要从这个环里再删掉一条边。

假设此时这条边连接的是 uu 和 vv 两个点，则从 uu 到 vv 的最短路径应该会经过 LCA(u,v)\text{LCA}(u,v)，所以这个环应该是从 uu 到 LCA(u,v)\text{LCA}(u,v) 再到 vv 最后回到 uu，因此，我们需要删掉的边应该是在从 uu 到 LCA(u,v)\text{LCA}(u,v) 再到 vv 这条路径上，又因为要求新的最小生成树的权值和最小，所以我们应该尽量删掉权值较大的边。

因此，这道题就变成了先求出最小生成树，然后对于每一条边，询问其两个端点在树上的最短路径中边权最大的边。

这种问题本来可以用树剖做，但由于没有修改操作，不需要那么麻烦其实就是懒，使用倍增求 LCA，在求每个点的第 2i2^i 个父亲的时候，另外开一个数组，求每个点到它第 2i2^i 个父亲这条路径上最大的边权，然后在往上跳的时候顺便用一个变量统计一下就可以了，具体的看代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
#define mp(a,b) make_pair(a,b)
#define pll pair<long long,long long>
using namespace std;
struct Edge
{
	long long u;
	long long v;
	long long c;
	long long id;
};
bool cmp(Edge a,Edge b)
{
	return a.c<b.c;
}
bool cmp2(Edge a,Edge b)//这个是求完最小生成树后还原所有边的顺序的，虽然也可以再开一个数组，但是我懒。
{
	return a.id<b.id;
}
Edge a[200001];
vector<pll> edge[200001];
long long n,m,cnt,k,log2n,f[200001],dep[200001],fa[200001][21],maxn[200001][21];
long long find(long long x)
{
	return f[x]==x? f[x]:f[x]=find(f[x]);
}
void dfs(long long u,long long father)
{
	fa[u][0]=father;
	dep[u]=dep[father]+1;
	for(long long i=1;(1<<i)<=dep[u];i++)
	{
		fa[u][i]=fa[fa[u][i-1]][i-1];
		maxn[u][i]=max(maxn[u][i-1],maxn[fa[u][i-1]][i-1]);//求 u 到它第 2^i 个父亲这条路径上最大的边权。
	}
	for(long long i=0;i<edge[u].size();i++)
	{
		long long v=edge[u][i].first,c=edge[u][i].second;
		if(v!=father)
		{
			maxn[v][0]=c;//在搜索儿子前先把这个初始化一下。
			dfs(v,u);
		}
	}
}
long long lca(long long u,long long v)
{
	long long depu=dep[u],depv=dep[v],ans=0;//ans 用来统计最大边权。
	if(depu!=depv)
	{
		if(depu<depv)
		{
			swap(depu,depv);
			swap(u,v);
		}
		for(long long i=0;(1<<i)<=depu-depv;i++)
			if((depu-depv)&(1<<i))
			{
				ans=max(ans,maxn[u][i]);
				u=fa[u][i];
			}
	}
	if(u==v)
		return ans;
	for(long long i=log2n;i>=0;i--)
		if(fa[u][i]!=fa[v][i])
		{
			ans=max(ans,max(maxn[u][i],maxn[v][i]));
			u=fa[u][i];
			v=fa[v][i];
		}
	return max(ans,max(maxn[u][0],maxn[v][0]));
}
signed main()
{
	scanf("%lld%lld",&n,&m);
	for(long long i=1;i<=n;i++)
		f[i]=i;
	for(long long i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld",&a[i].u,&a[i].v,&a[i].c);
		a[i].id=i;
	}
	sort(a+1,a+1+m,cmp);
	for(long long i=1;i<=m;i++)//Kruskal 求最小生成树。
	{
		long long t1=find(a[i].u),t2=find(a[i].v);
		if(t1!=t2)
		{
			f[t1]=t2;
			cnt++;
			k+=a[i].c;
			edge[a[i].u].push_back(mp(a[i].v,a[i].c));
			edge[a[i].v].push_back(mp(a[i].u,a[i].c));
		}
		if(cnt==n-1)
			break;
	}
	sort(a+1,a+1+m,cmp2);
	log2n=log(n)/log(2)+0.5;
	dfs(1,0);
	for(long long i=1;i<=m;i++)
		printf("%lld\n",k+a[i].c-lca(a[i].u,a[i].v));//加上当前这条的边权，删去路径上最大的边权。
	return 0;
}

一开始的时候我还想着要不要判断一下这条边是否是树边，但其实如果是树边的话，那么加上的也是它，删去的也是它，根本没有发生变化，所以没必要特判。

另外，这道题一定要开 long long，因为 109×2⋅10510^9\times 2\cdot10^5 很明显炸 int 了。