并查集进阶（个人笔记7）
柒葉灬
2018-08-27 22:12:01
## 巧用并查集
----
- #### 1.并查集可以处理的信息十分有限，它只能处理点到根的信息，切修改后不能撤回。
- #### 2.用并查集收集子树信息：
```cpp
void dfs(int f,int x){
fa[x]=x;
vis[x]=1;
for(int i=0;i<query[x];i++){
int y=query[x][i].to;
if(vis[y])solve(x,y);
//表示已经访问到了
}
for(int i=0;i<T[x].size();i++){
int y=T[x][i];
.......;
}
fa[x]=f;
return;
}
```
- #### 3.如果把并查集和其他数据结构相比，可以看到，
```cpp
int getfa(int x){
if(fa[x]!=x){
int t=fa[x];
fa[x]=getfa(fa[x]);
添加信息;
}
return fa[x];
}
```
#### 是不是很像延迟更新（lazy标记）？所以如果有类似询问区间的题目，把左端点挂到右端点，就可以离线进行回答。
- #### 4.例题，“最优贸易简易版”。
END