けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 070 D - Transit Tree Path (400 点)

一見、ツリー上のパスクエリ (オイラーツアーとかするやつ) な問題に見えるけど、そんなことはなかった

問題へのリンク

問題概要

 N 頂点のツリー (辺に重み付き) が与えられる。ツリー上の 1 点  K が与えられて、以下のクエリに  Q 個答えよ:

  • クエリ ( x, y):  x から  K を経由して  y へと至る方法のうち、移動距離の最小値を求めよ

制約

  •  3 \le N \le 10^{5}
  •  1 \le Q \le 10^{5}

考えたこと

ツリー上のパスの最短路を求めるクエリは LCA などを用いることでパッとできる典型題 (蟻本上級編に載ってる)。

が、そんな知識が 400 点問題で要求されるはずがなく...

ちょっと考えると今回のクエリは

  •  K から  x への最短経路長
  •  K から  y への最短経路長

を合計すればよい。 K がクエリごとに共通なのがポイントで、 K から各点 v への距離 dist[ v ] は高速に前処理計算できる。その前処理は

なんでもござれという感じ。ここではツリー上を DFS する感じでやってみた。

#include <iostream>
#include <vector>
using namespace std;

using Edge = pair<int, long long>;
using Graph = vector<vector<Edge> >;

void rec(const Graph &G, int v, int p, long long sum, vector<long long> &dist) {
    dist[v] = sum;
    for (auto e : G[v]) {
        if (e.first == p) continue;
        rec(G, e.first, v, sum+e.second, dist);
    }
}

int main() {
    int N; cin >> N;
    Graph G(N);
    for (int i = 0; i < N-1; ++i) {
        int a, b; long long c; cin >> a >> b >> c;
        --a, --b;
        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }
    int Q, K; cin >> Q >> K; --K;
    vector<long long> dist(N, 0);
    rec(G, K, -1, 0, dist);

    for (int q = 0; q < Q; ++q) {
        int x, y; cin >> x >> y; --x, --y;
        cout << dist[x] + dist[y] << endl;
    }
}