[AtCoder] ABC 126 D – Even Relation

2019年5月20日

問題

方針

最小共通祖先

根から 頂点 \( i \) までの距離を \(d_i \) とすると、頂点 \( u \) と 頂点 \( v \) の距離は、\( u \) と \( v \) の最小共通祖先までの距離 \( lca(u, v) \) を用いて、\( d_u + d_v – 2lca(u, v) \) で表せるそうです。参考として、競技プログラミングにおけるLAC問題で言及されていました。

ある頂点からの距離

上記の事実を利用すると、同じ色に塗った頂点間の距離が偶数ということは、ある頂点から同じ色の別の頂点までの距離が偶数ということです。全ての頂点間の距離を調べる必要はなく、一つの頂点からの距離を調べるだけでよいです。また、ある頂点からの距離が奇数の場合、その頂点は別の色で塗れば良いです。

例えば、頂点 \( 1 \) を基準として、全ての頂点の距離をしらべ、その距離が偶数であれば、\( 1 \) と同じ色、そうでなければ違う色にします。どう距離を求めるかですが、僕はダイクストラ法を用いて解きました。

コード

提出したコード (Java)

ダイクストラ法をC++で書き直したものを後で追加しようと思います。

提出したコード (C++)

ダイクストラ法

typedef long long ll;
static const ll INF = 100000000000000;

struct Node {
  int id;
  ll cost;
  Node() {}
  Node(int id, ll cost) : id(id), cost(cost){}
  bool operator< (const Node& node) const {
    return node.cost < cost;
  } 
};

// N: 頂点数, E: 辺の数, d: 距離 を格納する配列, 
// t: 始点, flag: true なら　無向辺, false なら 有向辺
void dijkstra(int N, int E, ll d[], int t, int from[], int to[], ll cost[], bool flag) {
  static const int WHITE = 0;
  static const int GRAY = 1;
  static const int BLACK = 2;
  
  int color[N];
  vector<Node> adj[N];
  for (int i = 0; i < N; i++) {
    d[i] = INF;
    color[i] = WHITE;
  }
  // 隣接リストの作成
  for (int i = 0; i < E; i++) {
    adj[from[i]].push_back(Node(to[i], cost[i]));
    if (flag) adj[to[i]].push_back(Node(from[i], cost[i]));
  }
  priority_queue<Node> pq;
  d[t] = 0;
  pq.push(Node(t, 0));
  while (!pq.empty()) {
    Node f = pq.top();
    pq.pop();
    int u = f.id;
    color[u] = BLACK;
    if (d[u] < f.cost) continue;
    for (int j = 0; j < adj[u].size(); j++) {
      int v = adj[u][j].id;
      if (color[v] == BLACK) continue;
      if (d[v] > d[u] + adj[u][j].cost) {
        d[v] = d[u] + adj[u][j].cost;
        pq.push(Node(v, d[v]));
        color[v] = GRAY;
      }
    }
  }
}