Never Wait for Weights http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1330

aoj1330.cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define chmin(a,b) (a)=min((a),(b));
#define chmax(a,b) (a)=max((a),(b));
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) cout<<(#v)<<":";for(auto(x):(v)){cout<<" "<<(x);}cout<<endl;
#define printVS(vs) cout<<(#vs)<<":"<<endl;for(auto(s):(vs)){cout<<(s)<< endl;}
#define printVV(vv) cout<<(#vv)<<":"<<endl;for(auto(v):(vv)){for(auto(x):(v)){cout<<" "<<(x);}cout<<endl;}
#define printP(p) cout<<(#p)<<(p).first<<" "<<(p).second<<endl;
#define printVP(vp) cout<<(#vp)<<":"<<endl;for(auto(p):(vp)){cout<<(p).first<<" "<<(p).second<<endl;}

inline void output(){ cerr << endl; }
template<typename First, typename... Rest>
inline void output(const First& first, const Rest&... rest) {
    cerr << first << " "; output(rest...);
}

using ll = long long;
using Pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
const int inf = 2e9;
const int mod = 1e9 + 7;

struct edge {
    int to, cost;
    edge(){}
    edge(int _to, int _cost) : to(_to), cost(_cost) {}
};
using Graph = vector<vector<edge>>;

class LCA {
private:
    static const int MAX_LOG = 20;
    const int n;
    Graph G;
    vector<vector<int>> par;
    vector<int> depth;
    vector<int> cost;

public:
    void bfs() {
        // v, p, d, c
        using State = tuple<int, int, int, int>;
        queue<State> que;
        que.push(State(0, -1, 0, 0));
        while (!que.empty()) {
            int v, p, d, c;
            tie(v, p, d, c) = que.front(); que.pop();
            par[0][v] = p;
            depth[v] = d;
            cost[v] = c;
            for (auto e : G[v]) {
                if (e.to != p) {
                    que.push(State(e.to, v, d + 1, c + e.cost));
                }
            }
        }
    }
    LCA(int _n) : n(_n), G(_n), par(MAX_LOG, vector<int>(_n)), depth(_n), cost(_n) {}
    void addEdge(int a, int b, int c) {
        G[a].emplace_back(b, c);
        G[b].emplace_back(a, -c);
    }
    void init(bool debug = false) {
        bfs();
        rep(i, MAX_LOG - 1) {
            rep(j, n) {
                if (par[i][j] == -1) {
                    par[i + 1][j] = -1;
                } else {
                    par[i + 1][j] = par[i][par[i][j]];
                }
            }
        }
    }
    int lca(int a, int b) {
        if (depth[a] > depth[b]) {
            swap(a, b);
        }
        rep(i, MAX_LOG) {
            if ((depth[b] - depth[a]) >> i & 1) {
                b = par[i][b];
            }
        }
        if (a == b) return a;

        rrep(i, MAX_LOG) {
            if (par[i][a] != par[i][b]) {
                a = par[i][a];
                b = par[i][b];
            }
        }
        return par[0][a];
    }
    int query(int a, int b) {
        int v = lca(a, b);
        return - (cost[a] - cost[v]) + cost[b] - cost[v];
    }
};

class UnionFind {
private:
    const int n;
    vector<int> uni;
public:
    UnionFind(int _n) : n(_n), uni(_n, -1) {}
    int root(int x) {
        if (uni[x] < 0) return x;
        return uni[x] = root(uni[x]);
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    bool unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (uni[x] > uni[y]) swap(x, y);
        uni[x] += uni[y];
        uni[y] = x;
        return true;
    }
    int getSize(int x) {
        return -uni[root(x)];
    }
    void print() {
        for (auto x : uni) cout << x << " ";
        cout << endl;
    }
};

struct Query {
    char t;
    int a, b;
    Query(){}
    Query(char t, int a, int b) : t(t), a(a), b(b) {}
    void disp() {
        output(t, a, b);
    }
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n, m;
    while (cin >> n >> m, n) {
        // s = 0: super root
        // v = 1, 2, ...: items
        const int s = 0;
        LCA lca(n + 1);
        UnionFind uf(n + 1);
        vector<Query> queries;
        rep(i, m) {
            char t;
            int a, b;
            cin >> t >> a >> b;
            queries.emplace_back(t, a, b);
            if (t == '!') {
                int c;
                cin >> c;
                if (uf.unite(a, b)) {
                    lca.addEdge(a, b, c);
                }
            }
        }

        rep2(i, 1, n + 1) {
            // connect s and the one of groups
            if (uf.unite(s, i)) {
                lca.addEdge(s, i, 0);
            }
        }

        lca.init();

        {
            UnionFind uf(n + 1);
            for (const auto& q : queries) {
                if (q.t == '!') {
                    uf.unite(q.a, q.b);
                }
                else {
                    if (uf.same(q.a, q.b)) {
                        cout << lca.query(q.a, q.b) << endl;
                    }
                    else {
                        cout << "UNKNOWN" << endl;
                    }
                }
            }
        }
    }
}