Steven_MengのBlog

传送门

考虑先把这张图的最小生成树$G$建出来,假设查询的边为$E$,

发现:

$1.$如果$E$本来就在$G$里面,那么直接输出$G$的边权和,因为没有比这个更优的解。

$2.$如果$E$不在$G$里面,那么$E$一定和$G$ 形成一个环,根据贪心的原则,我们把这条环上面最大边权的边删去,这样新的图仍然是一棵树,而且边权和最小。

在实际操作过程中,我们并不用找到那个环,可以这么想,假设$E$的端点分别为$u,v$,在最小生成树上它们的$LCA$为$alb$,那么这个环一定是由$u,alb$这条链,$alb,v$这条链和边$E$所构成,于是,只要找到路径$u,v$上面边权最大的一条边即可。

具体实现时,可以使用树上倍增或树链剖分。

注意:

$1.$求完最小生成树之后,一定要把按边权排序过的$E$数组还原。

$2.$$\rm QueryChain$和$\rm Query$不要写混。

$3.$要开$\rm long$ $\rm long$

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <bits/stdc++.h>
#define MAXN 400005
#define int long long
using namespace std;
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<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
struct Node{
int to,w;
};
vector<Node>G[MAXN];
inline void AddEdge(int u,int v,int w){
G[u].push_back(Node{v,w});
}
int sz[MAXN],big[MAXN],fa[MAXN],top[MAXN],dep[MAXN],tofa[MAXN];
void dfs1(int u,int father){
fa[u]=father;sz[u]=1;
for (register int i=0;i<G[u].size();++i){
int v=G[u][i].to,w=G[u][i].w;
if (v!=father){
dep[v]=dep[u]+1;
dfs1(v,u);
tofa[v]=w;
sz[u]+=sz[v];
if (sz[big[u]]<sz[v]) big[u]=v;
}
}
}
int seq[MAXN],cnt;
int alb[MAXN];
void dfs2(int u,int t){
alb[seq[u]=++cnt]=u;
top[u]=t;
if (big[u]) dfs2(big[u],t);
for (register int i=0;i<G[u].size();++i){
int v=G[u][i].to;
if (v!=fa[u]&&v!=big[u]){
dfs2(v,v);
}
}
}
namespace SegmentTree{
struct node{
int l,r;
int val;
}tree[MAXN<<2];
#define lc i<<1
#define rc i<<1|1
inline void pushup(int i){
tree[i].val=max(tree[lc].val,tree[rc].val);
}
void Build(int i,int l,int r){
tree[i].l=l,tree[i].r=r;
if (l==r) {
tree[i].val=tofa[alb[l]];
return ;
}
int mid=(l+r)>>1;
Build(lc,l,mid);
Build(rc,mid+1,r);
pushup(i);
}
int Query(int i,int L,int R){
if (L<=tree[i].l&&tree[i].r<=R){
return tree[i].val;
}
int mid=(tree[i].l+tree[i].r)>>1,ans=0;
if (L<=mid) ans=max(ans,Query(lc,L,R));
if (mid<R) ans=max(ans,Query(rc,L,R));
return ans;
}
}
using namespace SegmentTree;
inline int Query_Chain(int u,int v){
int ans=0;
while (top[u]!=top[v]){
if (dep[top[u]]<dep[top[v]]){
swap(u,v);
}
ans=max(ans,Query(1,seq[top[u]],seq[u]));
u=fa[top[u]];
}
if (dep[u]>dep[v]) swap(u,v);
return max(ans,Query(1,seq[u]+1,seq[v]));
}
int n;
inline void Init(){
dep[1]=1;
dfs1(1,0);
dfs2(1,1);
}


struct Edge{
int u,v,w,id;
}E[MAXN];
int tot;
inline void AddEdge1(int u,int v,int w){
E[++tot]=Edge{u,v,w,tot};
}
inline bool cmp1(const Edge &A,const Edge &B){return A.w<B.w;}
inline bool cmp2(const Edge &A,const Edge &B){return A.id<B.id;}
namespace BCJ{
int Fa[MAXN];
inline void Init_BCJ(){for (register int i=0;i<MAXN;++i) Fa[i]=i;}
inline int Get_Fa(int i){return Fa[i]==i?i:Fa[i]=Get_Fa(Fa[i]);}
}
using namespace BCJ;
int MST[MAXN];//这条边在MST中出现过
int Size;//生成树大小
inline void Kruscal(){
sort(E+1,E+1+tot,cmp1);
Init_BCJ();
Size=0;
for (register int i=1;i<=tot;++i){
int fau=Get_Fa(E[i].u),fav=Get_Fa(E[i].v);
if (fau!=fav){
AddEdge(E[i].u,E[i].v,E[i].w);
AddEdge(E[i].v,E[i].u,E[i].w);
Fa[fau]=fav;
Size+=E[i].w;
MST[E[i].id]=true;
}
}
sort(E+1,E+1+tot,cmp2);//再给他sort回去
}
#undef int
int main(){
#define int long long
int n=read(),m=read();
for (register int i=1;i<=m;++i){
int u=read(),v=read(),w=read();
AddEdge1(u,v,w);
}
Kruscal();
Init();//在生成树上面跑树链剖分
Build(1,1,n);
for (register int i=1;i<=m;++i){
if (MST[i]){
printf("%lld\n",Size);
}
else {
printf("%lld\n",Size-Query_Chain(E[i].u,E[i].v)+E[i].w);
}
}
}

 评论