求助次小生成树的的写法问题
查看原帖
求助次小生成树的的写法问题
387908
Vanilla_0楼主2021/10/2 16:55

查询函数中的两种写法,两种都能AC,第二种过不了样例。

求问哪种写法是对的。

第一种:

int query(int x,int y,int z)
{
	int v1=0,v2=0;
	if(d[x]>d[y]) swap(x,y);
	for(int i=20;i>=0;i--)
		if(d[f[y][i]]>=d[x]) 
		{
			v1=max(v1,mx[y][i]);
			if(i>0) v2=max(v2,get(y,i));
			y=f[y][i];
		}
	if(x==y) 
	{
		if(z>v1) return ans-v1+z;
		if(z==v1) return ans-v2+z;
	}
	for(int i=20;i>=0;i--)
		if(f[x][i]!=f[y][i])
		{
			v1=max(v1,mx[x][i]);
			if(i>0) v2=max(v2,get(x,i));
			v1=max(v1,mx[y][i]);
			if(i>0) v2=max(v2,get(y,i));
			x=f[x][i],y=f[y][i];
		}
	v1=max(v1,max(mx[x][0],mx[y][0]));
	v2=max(v2,max(mx[x][0],mx[y][0]));//?
	if(z>v1) return ans-v1+z;
	if(z==v1) return ans-v2+z;
}

第二种和第一种的区别

v2=max(v2,max(get(x,0),get(y,0)));
2021/10/2 16:55
加载中...