题解中的 $\text{lca}$ 函数都是用并查集查询花根跑的,复杂度可以均摊.

但是 $\text{shrink}$ 函数中并没有用并查集跳,而是直接暴力一格一格跳.

请问这样复杂度如何保证?

给个第一篇题解的代码:

int lca(int u,int v)//寻找两个节点的总花根 
{
	++cnt;//每次lca选用不同的cnt作为判断条件 
	u=get_fa(u);//保证操作对象时刻为分花根 
	v=get_fa(v);
	while(vis[u]!=cnt)//某一点同时两次被染色，即为总花根 
	{
		vis[u]=cnt;
		u=get_fa(pre[match[u]]);//保证操作对象时刻为分花根 
		if(v)swap(u,v);//切换操作对象 
	}
	return u;
}
void shrink(int u,int v,int r)//以r为总花根，将花缩成花根一点，并建立内部的反向pre
{
	while(get_fa(u)!=r)//当已达到总花根，说明缩花任务完成 
	{
		//每次循环起初的v为上个匹配的v 
		pre[u]=v;//建立反向pre，保证増广路
		v=match[u];
		if(col[v]==2){col[v]=1;q.push(v);}//花内所有v，都应以u身份向外増广 
		if(get_fa(u)==u)fa[u]=r;//如果某一点为分花根，将其合并到总花根上 
		if(get_fa(v)==v)fa[v]=r;
		u=pre[v];//切换操作对象 
	}
}