查询函数中的两种写法,两种都能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)));