很神奇的东西
%%%XCdalao考完试给我说：我好菜啊：我不会记录边权就开了点
%%%他考场发明了Kruskal重构树
Kruskal重构树的特点是：
由于边权的单调性于是父亲节点权值大于儿子节点
而且只有叶子节点才是真实的节点
Kruskal重构树的性质：
LCA的权就是瓶颈
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int N=2e5+100;
inline void read(int &x){
x=0;
char ch=getchar();
int f=1;
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
x*=f;
}
struct Front_star{
int u,v,w,nxt;
}e[N*4];
int cnt=0;
int head[N]={};
void Insert(int u,int v){
cnt++;
e[cnt].u=u;
e[cnt].v=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
int n,m;
bool cmp(Front_star A,Front_star B){
return A.w<B.w;
}
int fa[N]={};
int tot;
int st[N][21]={};
int dep[N]={};
void dfs(int u,int fat){
// cout<<u<<" "<<fat<<'\n';
st[u][0]=fat;
for(int i=1;i<=18;i++){
st[u][i]=st[st[u][i-1]][i-1];
}
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(v==fat)continue;
dep[v]=dep[u]+1;
dfs(v,u);
}
}
int GetLCA(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=20;i>=0;i--){
if(dep[x]-(1<<i)>=dep[y])x=st[x][i];
}
// cout<<x<<" "<<y<<'\n';
if(x==y)return x;
for(int i=20;i>=0;i--){
if(st[x][i]!=st[y][i]){
x=st[x][i];
y=st[y][i];
}
}
return st[x][0];
}
int val[N]={};
inline int getfa(int x){
if(fa[x]==x)return x;
else return fa[x]=getfa(fa[x]);
}
int main(){
// freopen("BZOJ3732.in","r",stdin);
read(n);
int K;
tot=n;
read(m);
read(K);
for(int i=1;i<=m;i++){
read(e[i].u);
read(e[i].v);
read(e[i].w);
}
cnt=m;
sort(e+1,e+1+m,cmp);
for(int i=1;i<=2*n;i++)fa[i]=i;
for(int i=1;i<=m;i++){
// cout<<e[i].w<<'\n';
int u=e[i].u;
int v=e[i].v;
if(getfa(u)!=getfa(v)){
tot++;
Insert(tot,getfa(u));
Insert(tot,getfa(v));
fa[getfa(u)]=tot;
fa[getfa(v)]=tot;
val[tot]=e[i].w;
}
}
/*for(int i=n+1;i<=tot;i++){
cout<<val[i]<<'\n';
}*/
// cout<<tot<<'\n';
dfs(tot,0);
while(K--){
int A,B;
read(A);
read(B);
// cout<<GetLCA(A,B)<<" ";
cout<<val[GetLCA(A,B)]<<'\n';
}
}
转播
