题目传送门：https://www.acwing.com/problem/content/241/
//懒得手敲题目
先给一下题解：
#include<iostream>
#include<unordered_map>
//这个题目有两个点要想明白，一个是点到根的距离标志着这个点的性质，且在路径压缩的过程中此点不会改变
//第二点就是在出现新的关系，也就是要将两个集合合并到一起的时候，一个点到根的距离是偶数表示是同性的，可能是同奇或者同偶
//合并的时候，
using namespace std;
const int N=1000010;
int fa[N],d[N];
unordered_map<int,int>s;
int n,m;
int find(int x)
{
if(fa[x]==x) return fa[x];
else{
int px=find(fa[x]);
d[x]+=d[fa[x]]; //px是已经被更新过的值，不可用fa[x]去更新
fa[x]=px;
}
return fa[x];
}
int get(int x)
{
if(!s.count(x)) s[x]=++n;
return s[x];
}
int main()
{
cin>>m>>m;
n=0;
int l,r,t,res; string s;
for(int i=1;i<N;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
cin>>l>>r>>s;
if(s=="even") t=0;
else t=1;
//直接判断信息之前是不是已经给出了
int x=get(l-1),y=get(r);
int px=find(x),py=find(y); //d[x]+?+d[y]=t
if(px!=py)
{
fa[px]=py;
d[px]=abs(d[x]-d[y]-t);
}else
{
if(abs(d[x]-d[y])%2!=t)
{res=i-1;
break;} //找到直接返回
}
}
cout<<res<<endl;
}
最近一直在做并查集的题目，有些问题困扰许久，故在此以此题为契机来回答一下几个疑惑点。
（1）第一点：路径压缩的时候，修改点的边权究竟是+=d[rx]还是+=d[fa[x]]？
图中也给出了解释，是+=d[fa[x]]，因为递归得到的根结点，而d[fa[x]]表示父节点到根节点的距离，加上根节点的距离是没有意义的。所以是加上父节点到根节点的距离再去将父节点修改为根节点。
（2）类似于此的并查集中先看所给的值是否又同一个根节点是何含义呢？
这里就是已经给出的条件我一定是放到了同一个集合里面，只是每个点到根节点的距离不同，以此来维护各个点所在的群。像这个题目就是两个群。而食物链就是三个群。
最重要的一点是，矛盾一定产生于已经给出的条件，也就是已有的一个集合。新给出的条件暂时无法判断，直接就放到了集合里面。
还有就是这个题目简化了多种情况，使得代码非常简洁，但同时也非常难理解。
关于此题，我也些问题：
（1）路径压缩为何不会改变每个点到根节点的奇偶性呢？
在图中给出解释，假如这个时候要查询4的祖先。那么就要路径压缩，同时假如之前的点都没有过路径压缩。可以看出每个点此时维护的都只是和父亲结点的奇偶性，而在路径压缩之后，就是对根节点（此时也就是每个结点的父节点）的奇偶性质（图中未给出）。比方说，假如1是奇，2到它的距离为1，所以2是偶数，3在路径压缩之前是偶数（到2的距离是2），3作完路径压缩之后到1的距离是3，与压缩之前和1结点的奇偶性是一致的。以此类推。这点也困扰我许久，因为暂时还未看异或处理的压缩方法。
（2）合并集合是怎么计算距离的？
这里我就懒得画图，直接想象吧。假如x的根节点是px,y的根节点是py，然后要将px指向py,同时计算px到py新的距离。
这里的t表示x和y是否是同奇偶性质的，如果是0表示同奇或者同偶，如若是1，则一为奇一为偶。
(d[x]+?+d[y])%2==t
这里很神奇，因为这个数随便是啥都行。d[x]-d[y]-t,-+随意组合答案都是对的（加绝对值）。
这是为什么呢？一方面我觉得可能什模2的特殊性（食物链绝无此性质），一方面所有情况也确实都包含进去了。
d[x]为奇数，d[y]为奇数，t=0 或者1 ，一共有八种组合，也的确八种情况都是对的，简直神奇！！
不过严格来讲，还是食物链的推法更合理且适用。