一些话
这b题目细节太多了，对刚起步的新人非常不友好，写的我想紫砂
写题时得画图理解
流程
带权并查集：食物链
父节点数组，距离数组
find函数：
//由于是将所有节点的指向根节点，而只有最上层的节点是直接指向根节点，所以是自上而下的操作，自下而上的递归。
如果f[x] != x
//储存find(f(x))
int t = find(fx);
//自上而下递归保证d[x]原本储存的是x到f[x]的距离，d[f[x]] 储存的是f[x]到根节点的距离
d[x] += d[f[x]];
f[x] = t;
//由于是自上而下的操作，所以操作写在递归语句后
返回f[x]
//由于是改变f[x] 的值，所以返回值也是f[x]
main函数:
读入n，m
初始化父节点数组
cnt声明
int cnt = 0;
while（m--){
读入op，x，y；
如果x或y>n，假话
else{
fx = find(x),fy = find(y);
如果op是1，
如果x，y不在一个集合，将x集合插到y中
//注意不能直接用else，要else if(fa != fb)确定是因为不在一个集合才没有进入上一条if语句
x根节点的父节点设为y的根节点(即f[x] = x的形式）
x原根节点到新根节点的距离d[x]设为y到根节点距离-x到原根节点距离（根节点变更，所以d[x] + d[fx] 才和d[y]相等，下面同理)
d[fx] = d[y] - d[x];
如果op是2，
如果x,y在同一个集合（根节点相同）且x和y到根节点距离差 - 1 再模3不为零，假话
如果x，y不在一个集合，将x集合插到y中
x根节点的父节点设为y的根节点(即f[x] = x的形式
x原根节点到新根节点的距离d[f[x]设为y到根节点距离-x到原根节点距离
}
输出假话数
return 0;
}
套路
带有维护信息的路径压缩
条件：并查集中要维护信息
int find(int x){ if(f[x] != x){ int t = find(f[x]; d[x] += d[f[x]; f[x] = t; } return f[x]; }
ac代码
#include <iostream> using namespace std; const int N = 5e4 + 10; int f[N],d[N]; int find(int x){ if(f[x] != x){ d[x] += d[f[x]]; f[x] = find(f[x]); } return f[x]; } int main(){ int n,m; scanf("%d%d",&n,&m); for(int i = 1;i <= n;i++) f[i] = i; int cnt = 0; while(m--){ int op,a,b; scanf("%d%d%d",&op,&a,&b); if(a > n || b > n){ cnt++; } else{ int fa = find(a); int fb = find(b); if(op == 1){ if(fa == fb && (d[a] - d[b]) % 3) cnt++; else if(fa != fb) { f[fa] = fb; d[fa] = d[b] - d[a]; } } else { if(fa == fb && (d[a] - d[b] - 1) % 3) cnt++; else if(fa != fb){ f[fa] = fb; d[fa] = d[b] - d[a] + 1; } } } } printf("%d\n",cnt); return 0; }
![【洛谷】【动态规划】P1002 [NOIP2002 普及组] 过河卒](https://ucc.alicdn.com/pic/developer-ecology/e0a754f7c32249babcf70d5468e5d7b8.png?x-oss-process=image/resize,h_160,m_lfit)