【BZOJ 3732】 Network Kruskal重构树+倍增LCA

Kruskal重构树裸题，

Sunshine互测的A题就是Kruskal重构树，我通过互测了解到了这个神奇的东西。。。

理解起来应该没什么难度吧，但是我的Peaks连WA，，，

省选估计要滚粗了TwT

#include<cstdio>

#include<cstring>

#include<algorithm>

#define for1(i,a,n) for(int i=(a);i<=(n);i++)

#define for2(i,a,n) for(int i=(a);i<(n);i++)

#define for3(i,a,n) for(int i=(a);i>=(n);i--)

#define for4(i,a,n) for(int i=(a);i>(n);i--)

#define read(x) x=getint()

#define CC(i,a) memset(i,a,sizeof(i))

using namespace std;

inline const int getint(){char c=getchar();int k=1,r=0;for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1;for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';return k*r;}

inline const int max(const int &a,const int &b){return a>b?a:b;}

inline const int min(const int &a,const int &b){return a<b?a:b;}

inline void swapp(int &a,int &b){int c=a;a=b;b=c;}

const int N=15003;

const int M=30003;

struct node{int x,y,z;}E[M];

int n,m,lch[N<<1],rch[N<<1],num[N<<1],f[N<<1][16],fa[N<<1],deep[N<<1],cnt;

inline void init(){CC(lch,0);CC(rch,0);CC(num,0);CC(f,0);CC(fa,0);CC(deep,0);}

inline bool cmp(node X,node Y){return X.z<Y.z;}

inline int find(int X){

	if (fa[X]==X) return X;

	else {fa[X]=find(fa[X]); return fa[X];}

}

inline void LCA(){

	for1(j,1,15)

		for2(i,1,n<<1)

			if (f[f[i][j-1]][j-1]!=0) f[i][j]=f[f[i][j-1]][j-1];

}

inline void dfs(int x){

	if (lch[x]) {deep[lch[x]]=deep[x]+1; dfs(lch[x]);}

	if (rch[x]) {deep[rch[x]]=deep[x]+1; dfs(rch[x]);}

}

inline int LCA_find(int u,int v){

	if (deep[u]<deep[v]) swapp(u,v);

	int dis=deep[u]-deep[v];

	for1(i,0,15)

		if ((1<<i)&dis) u=f[u][i];

	if (u==v) return u;

	for3(i,15,0) if (f[u][i]!=f[v][i]){u=f[u][i]; v=f[v][i];}

	return f[u][0];

}

int main(){

	init(); int K;

	read(n); read(m); read(K);

	for1(i,1,m) {read(E[i].x);read(E[i].y);read(E[i].z);}

	sort(E+1,E+m+1,cmp);

	cnt=n+1;

	for2(i,1,n<<1) fa[i]=i;

	for1(i,1,m){

		int fx=find(E[i].x),fy=find(E[i].y);

		if (fx==fy) continue;

		fa[fx]=cnt; fa[fy]=cnt;

		f[fx][0]=cnt; f[fy][0]=cnt;

		lch[cnt]=fx; rch[cnt]=fy;

		num[cnt]=E[i].z;

		cnt++; if (cnt>(n<<1)-1) break;

	}

	LCA();

	deep[(n<<1)-1]=1;

	dfs((n<<1)-1);

	int a,b,rt;

	for1(i,1,K){

		read(a); read(b);

		rt=LCA_find(a,b);

		printf("%d\n",num[rt]);

	}return 0;

}

　　然后就完了