题目
BZOJ1202 [HNOI2005]狡猾的商人
分析
用并查集维护各节点到各自根节点的前缀和。将[x,y]的信息保存在y上，在路径压缩过程中，边压缩边计算前缀和。
值得注意的是，计算[x,y]时应当合并[x-1,y]，这样可以方便的判断两段区间是不是相邻组成了一个更大的区间。当这个区间已经有值时，可以直接v[y]-v[x]求出现在加入的这段区间的和，判断是否与现在加入的这段小区间的值相等。
这样做的精华在于：把这个区间的根节点提到x的前一个节点x-1上，那么如果之后碰到的某个y就是x-1，就可以直接合并成大区间，因为并查集森林中现在的y和相邻区间的x就是同一个节点，换句话说，两棵树具有共同的根。那么合并时不就完全不需要特判就可以很自然的把信息统一到根（即已有的x-1，或现在的y）。而不需要每次合并时都先判断y+1是否有值，然后先合并当前区间，再把现在这两个相邻的区间合并的费尽操作。
细节上要注意维护前缀和时，因为我们合并的就是(x-1,y)，所以不需要再通过v[y]-v[x-1]求前缀和，而是直接算v[y]-v[x]。我的代码里全部都是从0开始减去每一次的值，换句话说，如果亏损就相当于在区间里加上了这个金额。当然也可以正负反过来写，但不如这样便于理解（浏览代码即可明白）。
代码
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1002;
int fa[maxn],v[maxn];
int n,m,T;
bool flag;int Find(int x)
{if(fa[x]==x) return x;int p=Find(fa[x]);
//注意：要先保存父亲再加权值，否则在递归中每一段就各自被每一层多算了一次，然而即使和下一行交换顺序也能过样例……v[x]+=v[fa[x]]; fa[x]=p;return fa[x];
}void Union(int x,int y,int w)
{int p=Find(x),q=Find(y);if(p!=q){fa[p]=q;v[p]=v[y]-v[x]-w;//也可以改为+w，那么else if就改为！=-w.（理论上是对的）}else if(v[y]-v[x]!=w) flag=1;
}int main()
{scanf("%d",&T);while(T--){memset(v,0,sizeof(v));//记得要清空。，。flag=0;scanf("%d%d",&n,&m);for(int i=0;i<=n;i++) fa[i]=i;for(int i=1,x,y,z;i<=m;i++){scanf("%d%d%d",&x,&y,&z);if(!flag) Union(x-1,y,z);}if(flag) printf("false\n");else printf("true\n");}return 0;
}