题目链接：
K - Find them, Catch them
题目大意：警方决定捣毁两大犯罪团伙：龙帮和蛇帮，显然一个帮派至少有一人。该城有N个罪犯，编号从1至N（N<=100000。将有M（M<=100000）次操作。
D a b 表示a、b是不同帮派
A a b 询问a、b关系。
具体思路：带权并查集模板题。一般并查集都是相同的放在一个联通块里面。对于这个题，我们可以利用一下这个性质，只要是有联系的，都放进一个连通块里面，然后我们查询的时候，如果说他们的祖先一样的话，就首先能够保证是有关系的。然后就开始判断是敌对关系还是朋友关系。我们再加一个数组r[x]，表示x和他的祖先的关系，如果r[x]=1代表和祖先是敌对关系，否则就是朋友关系。然后在寻找路径的过程中，不停地更新就可以了。
#include<iostream>
#include<stdio.h>
#include<map>
using namespace std;
# define ll long long
# define inf 0x3f3f3f3f
const int maxn = 2e5+;
int father[maxn];
int r[maxn];
int Find(int t)
{
if(t==father[t])
return t;
int tmp=father[t];
father[t]=Find(father[t]);
r[t]=(r[tmp]+r[t])%;
return father[t];
}
void match(int t1,int t2)
{
int s1=Find(t1);
int s2=Find(t2);
father[s1]=s2;
r[s1]=(r[t1]+r[t2]+)%;//t1和t2是敌对关系
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,m;
scanf("%d %d",&n,&m);
for(int i=; i<=n; i++)
{
father[i]=i;
r[i]=;
}
char str[];
int st,ed;
while(m--)
{
scanf("%s",str);
if(str[]=='A')
{
scanf("%d %d",&st,&ed);
if(Find(st)==Find(ed))
{
if(r[st]==r[ed])
{
printf("In the same gang.\n");
}
else
printf("In different gangs.\n");
}
else
{
printf("Not sure yet.\n");
}
}
else
{
scanf("%d %d",&st,&ed);
match(st,ed);
}
}
return ;
}
}