一、并查集
1、普通并查集
inline int father(int x)
{
if(fath[x]==x) return x;
return fath[x]=father(fath[x]);
}
inline void Union(int x,int y)
{
int f1=father(x),f2=father(y);
if(f1==f2) return;
fath[f1]=f2;
}
2、带权并查集
如图，$dis[u]$表示$u$到$root-u$的距离，此时要合并两颗树，则以$root-v$为新根，$dis[ru]=Relationship(u,v)+dis[v]-dis[u]$。
当路径压缩时，$dis[x]+=dis[fath[x]]$。
此时有个重点，假如关系类型种类为$P$，所有$dis$要模$P$，关系种类满足递增性，循环性，可理解为$P$个一循环。
重点例题: [HNOI2005]狡猾的商人 (多种关系), Rochambeau (三种关系) ,
原文：https://www.cnblogs.com/linda-fcj/p/9298033.html