对于find函数

y总的写法：

int find(int x)
{
    if(p[x] != x)
    {
        int tmp = find(p[x]);
        d[x] += d[p[x]];
        p[x] = tmp;
    }
    return p[x];
}

我灵光一闪，改成这样：

int find(int x)
{
    if(p[x] != x)
    {
        d[x] += d[p[x]];
        p[x] = find(p[x]);
    }
    return p[x];
}

以为能省一行代码，但结果是WA。

原因分析：

首先，d[x]最开始是指x到父节点的距离

如果没有路径压缩，那么d[p[x]]指的是p[x]到父节点的距离，则有：

// x到根节点的距离 = x到父节点的距离 + 父节点到父节点的距离
d[x] = d[x] + d[p[x]]; 

难怪会WA了，因为父节点的父节点不一定是根节点，导致距离计算错误

然后，要知道递归调用find(p[x])函数，其实完成了以下两件事：

1.p[x]至根节点之间的节点全部进行路径压缩；

2.p[x]至根节点之间的节点k，其d[k]已经变成节点k到根节点的距离，不再是只到父节点的距离；

至于为什么能做到第二件事，是因为find在递到根节点后，开始归，即回溯：

1.回溯到根节点的儿子，有

// 儿子到根节点的距离 = 儿子到根节点的距离 + 根节点到父节点的距离(0)
d[x] = d[x] + d[p[x]]; 

2.回溯到根节点的孙子，有

// 孙子到根节点的距离 = 孙子到儿子的距离 + 儿子节点到父节点的距离(儿子到根节点的距离)
d[x] = d[x] + d[p[x]]; 

3.回溯到根节点的曾孙子，有

// 曾孙子到根节点的距离 = 曾孙子到孙子的距离 + 曾孙子到父节点的距离(孙子到根节点的距离)
d[x] = d[x] + d[p[x]]; 

......

回溯写的很啰嗦，因为我自己想把过程理得更清楚些，就当做个备忘录。从这题可以看得出我递归学得不够扎实

故结论是：

必须先调用find递归，再更新节点距离