带权并查集按秩合并即可维护。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define N 100010 int n,m,fa[N],deep[N],weight[N],len[N]; int find(int x) { if (fa[x]==x) return x; int p=find(fa[x]); weight[x]=weight[fa[x]]+len[x]; return p; } void merge(int x,int y,int z) { int p=find(x),q=find(y); if (p!=q) { if (deep[p]<deep[q]) swap(p,q),swap(x,y),z=-z; fa[q]=p;if (deep[p]==deep[q]) deep[p]++; weight[q]=len[q]=weight[x]-weight[y]-z; } } int main() { #ifndef ONLINE_JUDGE freopen("bzoj4690.in","r",stdin); freopen("bzoj4690.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read(),m=read(); while (n) { for (int i=1;i<=n;i++) fa[i]=i,deep[i]=1,weight[i]=len[i]=0; while (m--) { char c=getchar(); while (c!='!'&&c!='?') c=getchar(); if (c=='!') { int x=read(),y=read(),z=read(); merge(x,y,z); } else { int x=read(),y=read(); if (find(x)!=find(y)) printf("UNKNOWN "); else printf("%d ",weight[x]-weight[y]); } } n=read(),m=read(); } return 0; }