1 . CF609E Minimum spanning tree for each edge
题意
给你 \(n\) 个点，\(m\) 条边，对于编号位i的边求出必须包含i的最小生成树权值和。
很好理解，不做赘述。
题解
前置芝士：Kruskal算法求最小生成树，ST表倍增。
首先，我们不考虑每条边的限制，先将整张图的最小生成树求出，连边建树并求权值和。
现在加入限制。
对于第 \(i\) 条边，如果 \(i\) 在最小生成树上，直接输出权值和即可。
不在的情况值得讨论。
假设我们直接在树上加入了第 \(i\) 条边，设 \(i\) 连接 \(u\) 和 \(v\)，那么我们在加入的同时需要断掉原最小生成树上 \(u\)，\(v\) 路径上的一条边，否则就不是一棵树了。
显而易见，设最小生成树权值和为 \(all\)，\(i\) 的边权为 \(w\) ，短边边权为 \(w'\)
则有 \(ans=all+w-w'\)
所以显然需要断掉 \(u\)，\(v\) 路径上边权最大的边。
求出这条边显然可以使用倍增。
所以整体思路就很清楚了，先建出最小生成树，再考虑每一条边，若在树上直接输出权值和，否则求个倍增最大值。结束了。
code
//writer:Oier_szc
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,m;
struct node
{
int u,v,w,id;
bool operator<(const node &W) const
{
return w<W.w;
}
}e[N];
int fa[N];
int find(int u)
{
if(fa[u]==u) return fa[u];
else return fa[u]=find(fa[u]);
}
void merge(int a,int b)
{
fa[a]=b;
}
int head[N],ne[N<<1],to[N<<1],w[N<<1],tot=0;
void add(int u,int v,int W)
{
to[++tot]=v;
w[tot]=W;
ne[tot]=head[u];
head[u]=tot;
}
bool in[N];
int ANS=0,p[20][N],deep[N],st[20][N];
void dfs(int u,int fa)
{
p[0][u]=fa;
deep[u]=deep[fa]+1;
for(int i=head[u];i;i=ne[i])
{
if(to[i]==fa) continue;
st[0][to[i]]=w[i];
dfs(to[i],u);
}
}
void init()
{
for(int i=1;i<20;++i)
{
for(int j=1;j<=n;++j)
{
if(p[i-1][j]!=-1)
{
p[i][j]=p[i-1][p[i-1][j]];
st[i][j]=max(st[i-1][j],st[i-1][p[i-1][j]]);
}
}
}
}
int LCA(int a,int b)
{
if(deep[b]>deep[a]) swap(a,b);
int maxn=0;
for(int i=19;i>=0;--i)
{
if(p[i][a]!=-1&&deep[p[i][a]]>=deep[b])
{
maxn=max(maxn,st[i][a]);
a=p[i][a];
}
}
if(a==b) return maxn;
for(int i=19;i>=0;--i)
{
if(p[i][a]!=-1&&p[i][a]!=p[i][b])
{
maxn=max(maxn,max(st[i][a],st[i][b]));
a=p[i][a];
b=p[i][b];
}
}
return max(maxn,max(st[0][a],st[0][b]));
}
int ans[N];
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;++i)
{
scanf("%lld%lld%lld",&e[i].u,&e[i].v,&e[i].w);
e[i].id=i;
}
sort(e+1,e+1+m);
int fu,fv;
for(int i=1;i<=n;++i) fa[i]=i;
for(int i=1;i<=m;++i)
{
fu=find(e[i].u);
fv=find(e[i].v);
if(fu==fv) continue;
merge(fu,fv);
add(e[i].u,e[i].v,e[i].w);
add(e[i].v,e[i].u,e[i].w);
in[e[i].id]=true;
ANS+=e[i].w;
}
dfs(1,-1);
init();
for(int i=1;i<=m;++i)
{
if(in[e[i].id]) ans[e[i].id]=ANS;
else
{
ans[e[i].id]=ANS+e[i].w-LCA(e[i].u,e[i].v);
}
}
for(int i=1;i<=m;++i)
{
printf("%lld\n",ans[i]);
}
return 0;
}
2 . CF888G Xor-MST
前置芝士：Boruvka算法，01Trie
题意
给你一张最多有 \(2 \times 10^5\) 个点的完全图，两两之间边权为两点点权的异或，让你求最小生成树。
题解
又神又难写的题。
对于完全图的最小生成树，显然Prim和Kruskal都难以胜任，这道题涉及到了一个全新的算法叫Boruvka算法。
Boruvka算法流程
其实和Kruskal很类似。首先还是并查集。
先将所有单个点的祖先调整成自己。然后开始合并连通块。
对于每一次合并，我们找到每一个连通块的点连到其它连通块的最小的一条边，然后将两个连通块合并。有一小点分治的味道。
当然，这里要注意是，可能会出现重边的情况。例如连通块A连出去到了连通块B，但连通块B连出去的最小边正好是集合A，不判重会算两次，会出问题。
对于复杂度，首先看每一次合并，显然是\(O(E)\)；然后看合并次数，可以发现每次合并连通块数量至少减半，所以最多合并\(O(log\ N)\)次，总复杂度自然是\(O(E\ log\ N)\)。
如果想深入学习该算法可以右转oi-wiki。
回到题目x1
直接套这个算法怎么行，边都到 \(10\) 的 \(10\) 次方级别了。
考虑优化找到最小边的过程。
考虑枚举每一个点。对于一个点，如果想找到与其异或起来的最小值，有一个很常用的套路。那就是01Trie。
如何找呢？再看一道模板题。
最长异或路径
不妨将每一个数变成二进制串，从高往低位插入字典树。
考虑访问。根据贪心的思想，对于一个数 \(a\) 的二进制表示，显然在访问的过程中要使得最高位尽可能与 \(a\) 不同，因为最高位比下面几位都大，显然这样才能将异或结果最大化。
所以问题的解显而易见，在访问时从最高位开始尽可能的与 \(a\) 不同，最后返回值即可。
回到题目x2
同理，我们就可以通过01Trie求出每个点连到其它连通块的最小值。只要将尽可能相反变成尽可能相同，即可将一次合并复杂度变为 \(O(N\ log\ V)\) 。
但是具体如何套进算法还有一堆细节。
显然，01Trie上访问时不能访问到当前连通块的元素。为解决，不妨将Trie想成一个普通的树，我们设 \(l[i]\) 和 \(r[i]\) ，表示 \(i\) 号点子树内所有元素所在连通块编号的最小值和最大值，那么当 \(l[to]=r[to]=id\)
（\(id\) 表示现在查询的元素所在的连通块）时，就不能进入子树 \(to\) 中访问。
还有一点就是每一轮Boruvka中的合并后要将整个Trie dfs一遍，更新01Trie内所有点的 \(l[i]\) 和 \(r[i]\)，这相对好办。
将所有细节整合起来，耐心码一下代码，你就能A一道上位紫了！
code
//writer:Oier_szc
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n;
long long ans=0;
int a[N];
int tr[N*32][2],ID[N*32],idx=0;
int l[N*32],r[N*32];
int fa[N];
inline int find(int u)
{
if(fa[u]==u) return fa[u];
else return fa[u]=find(fa[u]);
}
inline void insert(int x,int id)
{
int u=0;
for(register int i=29;i>=0;--i)
{
int to=(x>>i)&1;
if(!tr[u][to]) tr[u][to]=++idx;
u=tr[u][to];
}
ID[u]=id;
}
inline void dfs(int u)
{
if(ID[u])
{
l[u]=r[u]=find(ID[u]);
return;
}
l[u]=0x3f3f3f3f;
r[u]=0;
if(tr[u][0])
{
dfs(tr[u][0]);
l[u]=min(l[u],l[tr[u][0]]);
r[u]=max(r[u],r[tr[u][0]]);
}
if(tr[u][1])
{
dfs(tr[u][1]);
l[u]=min(l[u],l[tr[u][1]]);
r[u]=max(r[u],r[tr[u][1]]);
}
}
inline pair<int,int> query(int x,int id)
{
int u=0,res=0;
for(register int i=29;i>=0;--i)
{
int to=(x>>i)&1;
if(tr[u][to]&&!(l[tr[u][to]]==r[tr[u][to]]&&l[tr[u][to]]==id))
{
res=(res<<1)+to;
u=tr[u][to];
}
else if(tr[u][!to]&&!(l[tr[u][!to]]==r[tr[u][!to]]&&l[tr[u][!to]]==id))
{
res=(res<<1)+!to;
u=tr[u][!to];
}
else break;
}
return make_pair(res,ID[u]);
}
int best[N],bestid[N];
signed main()
{
scanf("%d",&n);
for(register int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
}
sort(a+1,a+1+n);
n=unique(a+1,a+1+n)-a-1;
for(int i=1;i<=n;++i)
{
fa[i]=i;
insert(a[i],i);
}
int cnt=0;
while(cnt<n-1)
{
for(register int i=1;i<=n;++i)
{
best[i]=0x3f3f3f3f;
}
dfs(0);
pair<int,int> qwq;
int fu,fv;
for(register int i=1;i<=n;++i)
{
fu=find(i);
qwq=query(a[i],fu);
fv=find(qwq.second);
if((a[i]^qwq.first)<best[fu])
{
best[fu]=(a[i]^qwq.first);
bestid[fu]=fv;
}
if((a[i]^qwq.first)<best[fv])
{
best[fv]=(a[i]^qwq.first);
bestid[fv]=fu;
}
}
for(register int i=1;i<=n;++i)
{
if(fa[i]!=i) continue;
if(best[i]<0x3f3f3f3f&&bestid[i]!=0)
{
if(bestid[bestid[i]]==i) bestid[bestid[i]]=0;//判重边
fa[i]=bestid[i];
ans+=best[i];
++cnt;
}
}
}
printf("%lld",ans);
return 0;
}