洛谷题面

题目大意

一张连通图，\(q\) 次询问从两个点 \(x\) 和 \(y\) 出发，希望经过的点(不重复)数量等于 \(z\)，经过的边最大编号最小是多少。

题目分析

什么是 \(\rm Kruskal\) 重构树

从下面的例子入手：

\(\rm Kruskal\) 最小生成树算法都知道吧 \(\verb!qwq!\)，该例最小生成树为：

我们按照 \(\rm Kruskal\) 的方式建树，设要连接的边为 \((u,v)\)，通过并查集可求得 \(u\) 的祖先节点为 \(x\)，\(v\) 的祖先节点为 \(y\)。

若 \(x\neq y\)，则新建一个节点 \(z\) 作为 \(x,y\) 的父亲来合并 \(x,y\)，\(z\) 的点权为边 \((x,y)\) 的长度。

最后我们建出来了一棵二叉树，具体长这样：

这棵树拥有以下性质：

• 叶子节点都是构成最小生成树的节点。

• 生成树中有 \(n\) 个节点，会产生 \(n-1\) 个含有点权的节点，共 \(n+n-1=2\cdot n-1\) 个节点。

• 按最小生成树重构的重构树是大根堆，按最大生成树重构的重构树是小根堆。

• 按最小生成树重构的重构树中任意两点 \(a,b\) 的路径中的最大边权为它们 \(\operatorname{LCA}(a,b)\) 的点权，也是 \(a,b\) 路径中最大边权的最小值，按最大生成树重构的重构树中任意两点 \(a,b\) 的路径中的最小边权为它们 \(\operatorname{LCA}(a,b)\) 的点权，也是 \(a,b\) 路径中最小边权的最大值。

模板代码：

namespace ex_Kruskal{
	// 注意数组开两倍! 
	
	int nowidx,idx;
	inline bool cmp1(Node x,Node y) { // 按最小生成树重构的重构树
		return x.w < y.w;
	}
	inline bool cmp2(Node x,Node y) { // 按最大生成树重构的重构树
		return x.w > y.w;
	}
	inline void add(int u,int v) {
		gra[++ idx].v = v,gra[idx].nxt = head[u];
		head[u] = idx;
	}
	
	inline void Kruskal() {
		for (register int i = 1;i <= n * 2 - 1; ++ i) {
			fa[i] = i;
		}
		sort (node + 1,node + m + 1,ex_Kruskal::cmp);
		
		nowidx = n;
		for (register int i = 1;i <= m; ++ i) {
			int x = getf(node[i].u),y = getf(node[i].v);
			if (x != y) {
				val[++ nowidx] = node[i].w;//存储当前节点的点权
				fa[x] = fa[y] = nowidx;
				
				add(nowidx,x),add(nowidx,y);
			}
		}
	}
}

应用

本题我们可以二分编号（显然满足单调性），对于询问 \(x,y\)，我们倍增向上跳到点权大于当前二分值的位置，然后再判断此时 \(x,y\) 跳到的节点 \(x',y'\) 的子树中的叶子节点数之和是否达到了 \(z\)。

如果没有达到 \(z\)，说明经过的点的数量少了，应该调大一点，即 \(l\gets mid+1\)；如果超过了 \(z\)，说明应该调小一点，即 \(r\gets mid-1\)；如果等于 \(z\)，那么此时的 \(mid\) 即为答案。

代码

//2022/2/8

//2022/2/9

#define _CRT_SECURE_NO_WARNINGS

#include 

#include 

#include //need "INT_MAX","INT_MIN"

#include //need "memset"

#include 

#define enter() putchar(10)

#define debug(c,que) cerr<<#c<<" = "<'9')
		{
			if(ch=='-')
			{
				k=-1;
			}
			ch=getchar();
		}
		while(ch>='0' && ch<='9')
		{
			x=(x<<1)+(x<<3)+ch-'0';
			ch=getchar();
		}
		return x*k;
	}
	inline void write(int x)
	{
		if(x<0)
		{
			putchar('-');
			x=-x;
		}
		if(x>9)
		{
			write(x/10);
		}
		putchar(x%10+'0');
	}
}

using namespace Newstd;

using namespace std;

const int ma=1e5+5;

struct Gragh
{
	int v;
	
	int nxt;
};

Gragh gra[ma<<1];

int head[ma<<1],fa[ma<<1],val[ma<<1],sons[ma<<1];

int fath[ma<<1][21];

int n,m,q;

int nowidx,idx;

inline void add(int u,int v)
{
	gra[++idx].v=v;
	
	gra[idx].nxt=head[u];
	
	head[u]=idx;
}

inline void dfs(int now,int dad)
{
	fath[now][0]=dad;
	
	for(register int i=1;i<=20;i++)
	{
		fath[now][i]=fath[fath[now][i-1]][i-1];
	}
	
	if(head[now]==0)
	{
		sons[now]=1;
		
		return;
	}
	
	for(register int i=head[now];i;i=gra[i].nxt)
	{
		int v=gra[i].v;
		
		if(v!=dad)
		{
			dfs(v,now);
			
			sons[now]+=sons[v];
		}
	}
}

namespace dsu
{
	inline int getf(int x)
	{
		return fa[x]==x?x:fa[x]=getf(fa[x]);
	}
}

namespace ex_Kruskal
{
	inline void Kruskal()
	{
		for(register int i=1;i<=n*2-1;i++)
		{
			fa[i]=i;
		}

		val[0]=INT_MAX;
		
		nowidx=n;
		
		for(register int i=1;i<=m;i++)
		{
			int u=read(),v=read();

			int x=dsu::getf(u),y=dsu::getf(v);
			
			if(x!=y)
			{
				val[++nowidx]=i;
				
				fa[x]=fa[y]=nowidx;
				
				add(nowidx,x),add(nowidx,y);
			}
		}
	}
}

namespace bs
{
	inline bool check(int now,int x,int y,int num)
	{
		for(register int i=20;i>=0;i--)
		{
			if(val[fath[x][i]]<=now)
			{
				x=fath[x][i];
			}
			
			if(val[fath[y][i]]<=now)
			{
				y=fath[y][i];
			}
		}
		
		if(x==y)
		{
			return sons[x]>1;
			
			if(bs::check(mid,u,v,w)==true)
			{
				l=mid+1;
			}
			
			else
			{
				r=mid-1;
				
				ans=mid;
			}
		}
		
		write(ans);
		
		enter();
	}
	
	return 0;
}