【树上倍增】最小瓶颈生成树-爱代码爱编程
随便学一下树上倍增,反正闲着也是闲着
一周没vpCf,感觉早该414了
下周vp abc!
至少能开出签到呜呜呜
【模板】最小瓶颈生成树(数据加强版) - 题目 - Daimayuan Online Judge
题意
思路:
其实就是去求树上某一路径的边的最大值
答案就是max(query(u,lca),query(v,lca))
然后可以用树上倍增维护到第j级祖先的路径的边权的最大值
其实不是很懂
感觉就是板子的嵌套QwQ
感觉以后用着用着应该就会懂了
Code:
#include <bits/stdc++.h>
using namespace std;
//#define int long long
using i64 = long long;
const int mxn=1e6+10;
const int mxe=1e6+10;
struct ty{
int to,next,w;
}edge[mxe<<1];
struct ty2{
int u,v,w;
}e[mxe<<1];
bool cmp(ty2 x,ty2 y){
return x.w<y.w;
}
int n,m,u,v,w,tot=0,Q;
int F[mxn][33],mx[mxn][33];
int head[mxn],f[mxn],dep[mxn];
void dfs_tree(int u,int fa){
F[u][0]=fa;
dep[u]=dep[fa]+1;
for(int j=1;j<=30;j++){
F[u][j]=F[F[u][j-1]][j-1];
mx[u][j]=max(mx[u][j-1],mx[F[u][j-1]][j-1]);
}
for(int i=head[u];~i;i=edge[i].next){
if(edge[i].to==fa) continue;
mx[edge[i].to][0]=edge[i].w;
dfs_tree(edge[i].to,u);
}
}
void init(){
tot=0;
for(int i=0;i<=n;i++){
head[i]=-1;
f[i]=i;
}
}
void add(int u,int v,int w){
edge[tot].w=w;
edge[tot].to=v;
edge[tot].next=head[u];
head[u]=tot++;
}
int find(int x){
return f[x]=(x==f[x])?x:find(f[x]);
}
void join(int u,int v){
int f1=find(u),f2=find(v);
if(f1!=f2) f[f1]=f2;
}
void kruskal(){
int res=0;
sort(e+1,e+1+m,cmp);
for(int i=1;i<=m;i++){
if(find(e[i].u)==find(e[i].v)) continue;
join(e[i].u,e[i].v);
add(e[i].u,e[i].v,e[i].w);
add(e[i].v,e[i].u,e[i].w);
res+=e[i].w;
}
}
int lca(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
for(int j=30;j>=0;j--){
if(dep[F[u][j]]>=dep[v]){
u=F[u][j];
}
}
if(u==v) return u;
for(int j=30;j>=0;j--){
if(F[u][j]!=F[v][j]){
u=F[u][j];
v=F[v][j];
}
}
return F[u][0];
}
int query(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
int res=-1e9;
for(int j=30;j>=0;j--){
if(dep[F[u][j]]>=dep[v]){
res=max(res,mx[u][j]);
u=F[u][j];
}
}
return res;
}
void solve(){
cin>>n>>m;
init();
for(int i=1;i<=m;i++){
cin>>u>>v>>w;
e[i]={u,v,w};
}
kruskal();
dfs_tree(1,0);
cin>>Q;
while(Q--){
cin>>u>>v;
int t=lca(u,v);
cout<<max(query(u,t),query(t,v))<<'\n';
}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int __=1;//cin>>__;
while(__--)solve();return 0;
}
最后贴一下树上倍增的板子:
void dfs(int u,int fa){
sz[u]=1;dep[u]=dep[fa]+1;
F[u][0]=fa;
for(int i=1;i<=30;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=edge[i].next){
if(edge[i].to==fa) continue;
mx[edge[i].to][0]=edge[i].w;
dfs(edge[i].to,u);
sz[u]+=sz[edge[i].to];
}
}