就这题,一直过不了,只对了#2,这是原来的 find 函数:
int find(int x)
{
if(fa[x]==x) return x;
dis[x]+=dis[fa[x]];
return fa[x]=find(fa[x]);
}
但是我看了看讨论版后改了一下,变成这样:
int find(int x)
{
if(fa[x]==x) return x;
int t=find(fa[x]);
//唯一的改变就是这里用了一个变量存起来
dis[x]+=dis[fa[x]];
fa[x]=t;
return fa[x];
}
就直接AC了,请问这是为什么啊?我普通并查集按照之前的写法写也没问题啊,难道说带权并查集一定要额外变量存?