AOJ1330 Never Wait for Weights - ferinの競プロ帳

問題ページ
Never Wait for Weights | Aizu Online Judge

考えたこと

bがaよりwグラム重いことを頂点bから頂点aへ重みがwの辺を張ることで表す
すると重さの差の質問クエリがある頂点からある頂点までの距離を求めるクエリに帰着できる
重さの差を測るクエリは辺を張ることで表す
質問クエリでその時点で2頂点が連結なら距離は絶対にわかる
逆に非連結なら"UNKNOWN"になる
余計に辺が張ってあったとしても関係ないのでクエリ先読みして辺を張っておいてよい
問題設定からすでに連結している2頂点間で辺を張るようなクエリは無視できる
無視できるクエリについて辺を張らないとするとグラフは森になる
森で2点間の距離を高速に求めるクエリ→LCAでよさそう
辺の重みの正負がその辺と逆辺で反対になるのに注意しつつ考える
いつものLCAみたいに考えると d[u] + d[v] - d[lca]*2 だけど上の通りこれはおかしい
vの方は正負が反転して (d[u] - d[lca]) - (d[v] - d[lca]) となる
lcaの部分が消えてd[u]-d[v]となる
つまり実はLCAが要らなくてdfsで根からの距離を求めればいいだけ

考察するとdfsするだけになって面白い

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define PB push_back

const ll LLINF = (1LL<<60);

class UnionFind {
public:
  const static int MAX_N = 100010;
  int par[MAX_N];
  int s[MAX_N];
  UnionFind() { init(); }
  UnionFind(int n) { init(n); }
  void init() { for(int i=0; i<MAX_N; ++i) par[i] = i, s[i] = 1; }
  void init(int n) { for(int i=0; i<n; ++i) par[i] = i, s[i] = 1; }
  int find(int x) {
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(s[x] < s[y]) par[x] = y, s[y] = s[x] + s[y];
    else par[y] = x, s[x] = s[x] + s[y];
  }
  bool same(int x, int y) { return find(x) == find(y);}
};
UnionFind uf;

vector<PII> g[100010];
int d[100010];
void dfs(int x, int p, int dist) {
  d[x] = dist;
  for(auto e: g[x]) {
    if(e.first != p) dfs(e.first, x, dist + e.second);
  }
}

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

  while(true) {
    int n, m;
    cin >> n >> m;
    if(!n) break;

    REP(i, n) g[i].clear();
    memset(d, 0, sizeof(d));
    uf.init(n);

    vector<PII> query;
    VI ans(m+5);
    int idx = 0;
    REP(i, m) {
      char c;
      int a, b;
      cin >> c >> a >> b; a--, b--;
      if(c == '!') {
        int w; cin >> w;
        if(!uf.same(a, b)) {
          uf.unite(a, b);
          g[a].PB({b, -w});
          g[b].PB({a, w});
        }
      } else {
        query.PB({a, b});
        if(!uf.same(a, b)) ans[idx] = LLINF;
        idx++;
      }
    }

    REP(i, n) if(d[i] == 0) dfs(i, -1, 0);

    REP(i, query.size()){
      if(ans[i]==LLINF) cout << "UNKNOWN" << endl;
      else cout << d[query[i].first] - d[query[i].second] << endl;
    }
  }

  return 0;
}