传送门
up[i] 表示一个木块上面有多少个
all[i] 表示整个连通块内有多少个
那么 一个木块下面的木块个数为 all[root[i]] up[i] 1
注意：up[i] 可以在 find 函数中维护，而 all[i] 不好维护，那么我们只需要祖先节点的 all[i] 表示整个连通块内木块的数目即可
合并时也注意维护
——代码
1 #include <cstdio> 2 #include <iostream> 3 #define N 1000001 4 5 int n; 6 int f[N], up[N], all[N]; 7 8 inline int read() 9 16 17 inline int find(int x) 18 25 return f[x]; 26 } 27 28 int main() 29 47 else 48 53 } 54 return 0; 55 }View Code
上一篇：[luoguP3690] 【模板】Link Cut Tree
下一篇：[BZOJ2594] [Wc2006]水管局长数据加强版（LCT + kruskal + 离线）
并查集
