AOJ1330 Never Wait for Weights

問題

Never Wait for Weights | Aizu Online Judge

考察

n<=100000
m<=100000
なのでn log mとか m log nにしたい気分。
連結判定はUnion Find使えばいい。
わりかしすぐに求められる情報が欲しい、どの情報があると便利か。
Union Find使うので、親との距離がわかっていれば、親との距離の差が答えになるのでは。
ということで、Union Findを少しいじって投げた。
uniteするときにどうやってくっつけるかちょっと手こずった。

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<functional>
#include<stack>
#include<queue>
#include <iomanip>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

#define DBG cerr << '!' << endl;
#define REP(i,n) for(int (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(int (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(int (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(10)

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

#define INF 10000000000

struct UF
{
	vector<int> par; // 親
	vector<int> sz; // 数
	vector<ll> value; // 量
	// 初期化
	UF(int n):par(n),sz(n),value(n) {
		for(int i = 0; i < n; i++){
			par[i] = i;sz[i] = 1;value[i] = 0;
		}
	}
	// 木の根を求める
	int find(int x) {
		if (par[x] == x)
		{
			value[x] = 0;
			return x;
		}
		else
		{
			int tmp = par[x];
			par[x] = find(par[x]);
			value[x] += value[tmp];
			//cout << x << ' ' << value[x] << endl;
			return par[x];
		}
	}
	ll retValue(int n)
	{
		find(n);
	//	cout << n << "s par is" << par[n] << ' ' << value[n] << endl;
		return value[n];
	}
	
	// xとyの属する集合を併合
	void unite(int x, int y,ll weight = 0) {
		int tmpx = x;int tmpy = y;
		x = find(x); y = find(y);
		if (x == y) return;
		par[x] = y;
		value[x] = -value[tmpx] + weight + value[tmpy];
	//	cout << "after unite" << x << "value is" << value[x] << ",par is" << par[x] << endl;
		sz[y] += sz[x];
	}
	// xとyが同じ集合ならtrue
	bool same(int x, int y) { return find(x) == find(y); }
	int size(int n){return sz[find(n)];}
};

int n,m;

int main()
{
	while(cin >> n >> m,n)
	{
		
		UF uf(n);
		
		REP(i,m)
		{
			char c;int a,b;
			cin >> c >> a >> b;
			a--;b--;
			if(c == '!')
			{
				int w;cin >> w;
				uf.unite(a,b,w);
			}
			else
			{
				if(!uf.same(a,b))
				{
					cout << "UNKNOWN" << endl;
				}
				else
				{
					ll A = uf.retValue(a);
					ll B = uf.retValue(b);
					cout << A-B << endl;
				}
			}
		}
	}
		
	
	return 0;
}