Kruskal 重构树

是一棵二叉树，一张 \(N\) 个点的无向连通图的 Kruskal 重构树有 \(2N-1\) 个节点。

叶子节点为原图中节点，非叶子节点有点权，表示想在原图上从一边的子树内的叶子节点所对应的原图上节点走到另一边的子树内的叶子节点所对应的原图上节点所需经过的最长边的最小可能值。

建树方式：Kruskal 每次合并 \(2\) 个节点时，新开一个点，记作这 \(2\) 个节点的重构树父亲（及并查集父亲），权值为当前这条边的权值。

代码如下：

（花15分钟敲完的模板题 [NOIP2013 提高组] 货车运输）

#include <bits/stdc++.h>

using namespace std;

const int MAXN=1e6+50;

int N,M;

struct Edge1

{

	int x,y,Len;

}E[MAXN];

struct Edge2

{

	int x,y,Next;

}e[MAXN<<1];

int elast[MAXN],tot;

void Add(int x,int y)

{

	tot++;

	e[tot].x=x;

	e[tot].y=y;

	e[tot].Next=elast[x];

	elast[x]=tot;

}

bool cmp(Edge1 a,Edge1 b)

{

	return a.Len<b.Len;

}

int father[MAXN];

int getfather(int x)

{

	if(x!=father[x])

	father[x]=getfather(father[x]);

	return father[x];

}

int f[MAXN][20],depth[MAXN];

int Val[MAXN];

void Kruskal()

{

	for(int i=1;i<=2*N-1;i++)

	{

		father[i]=i;

	}

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

	for(int i=1;i<=M;i++)

	{

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

		if(fx!=fy)

		{

			N++;

			father[fx]=N;

			father[fy]=N;

			Add(N,fx);

			Add(N,fy);

			Val[N]=E[i].Len;

		}

	}

}

void dfs(int u,int fa)

{

	depth[u]=depth[fa]+1;

	f[u][0]=fa;

	for(int i=1;f[f[u][i-1]][i-1];i++)

	{

		f[u][i]=f[f[u][i-1]][i-1];

	}

	for(int i=elast[u];i;i=e[i].Next)

	{

		int v=e[i].y;

		if(v==fa)

		continue;

		dfs(v,u);

	}

}

int GetLca(int x,int y)

{

	if(depth[x]<depth[y])

	swap(x,y);

	for(int i=19;i>=0;i--)

	{

		if(depth[f[x][i]]>=depth[y])

		{

			x=f[x][i];

		}

	}

	if(x==y)

	return x;

	for(int i=19;i>=0;i--)

	{

		if(f[x][i]!=f[y][i])

		{

			x=f[x][i];

			y=f[y][i];

		}

	}

	return f[x][0];

}

int main()

{

	scanf("%d%d",&N,&M);

	for(int i=1;i<=M;i++)

	{

		scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].Len);

		E[i].Len=-E[i].Len;

	}

	Kruskal();

	for(int i=N;i>=1;i--)

	{

		if(depth[i]==0)

		dfs(i,0);

	}

	int Q;

	scanf("%d",&Q);

	while(Q--)

	{

		int x,y;

		scanf("%d%d",&x,&y);

		int Lca=GetLca(x,y);

		if(Lca==0)

		puts("-1");

		else

		printf("%d\n",-Val[Lca]);

	}

}