传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4690
【题解】
带权并查集
fa[x]表示x的父亲，a[x]表示x到x的父亲多/少多少
那么找祖先的时候算一下到祖先多少，然后路径压缩。
合并的时候注意让fa[fx]=fy的时候，a[fx]是多少（这个可以算的）
然后查询直接做就行了。
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e5 + 10; const int mod = 1e9+7; # define RG register # define ST static int n, q; int fa[M], a[M]; inline int getf(int x) { int i=x, j, jj, res = 0; while(fa[x] != x) { res = res + a[x]; x = fa[x]; } while(i != x) { j = fa[i]; jj = a[i]; fa[i] = x; a[i] = res; res -= jj; i = j; } return x; } int main() { while(cin >> n >> q && (n+q)) { for (int i=1; i<=n; ++i) fa[i] = i, a[i] = 0; char opt[3]; int x, y, z; while(q--) { scanf("%s", opt); if(opt[0] == '!') { scanf("%d%d%d", &x, &y, &z); int fx = getf(x), fy = getf(y); if(fx == fy) continue; fa[fx] = fy; a[fx] = z-a[x]+a[y]; } else { scanf("%d%d", &x, &y); int fx = getf(x), fy = getf(y); if(fx != fy) puts("UNKNOWN"); else printf("%d\n", a[x]-a[y]); } } } return 0; } View Code
转载于:https://www.cnblogs.com/galaxies/p/bzoj4690.html
相关资源：JAVA上百实例源码以及开源项目