ABC070: D - Transit Tree Path

問題

D - Transit Tree Path

解説

与えられたグラフは木なので、2頂点間のパスは最短距離になる。 必ずKを通るので、まずKを起点としてDFSしてKからの距離dist_iを計算しておいて、各クエリについてdist_{a_i,K} + dist_{K,b_i}を求めればよい。

余談:はじめKが与えられていないと思って考えてしまった。その場合は適当に選んだ頂点に対して同様にDFSしてから、頂点を通るかどうかで場合分けをしてやると良いか思う。選んだ頂点の部分木ごとにUFしておくようにして、パスが部分木内で完結するか頂点を通るかの判定をするのが楽だろうか?

int N;
vector<vector<pair<int, int64_t>>> g;
vector<int64_t> dist;

void dfs(int curr, int par) {
  for (auto e: g[curr]) {
    int dest; int64_t cost; tie(dest, cost) = e;
    if (dest == par) continue;
    dist[dest] = dist[curr] + cost;
    dfs(dest, curr);
  }
}

int main() {
  cin >> N; g.resize(N);
  dist.resize(N);
  rep(i, N - 1) {
    int a, b, c; cin >> a >> b >> c;
    a--, b--;
    g[a].emplace_back(b, c);
    g[b].emplace_back(a, c);
  }
  int Q, K; cin >> Q >> K;
  K--;
  dfs(K, -1);
  rep(_, Q) {
    int x, y; cin >> x >> y;
    x--, y--;
    cout << dist[x] + dist[y] << "\n";
  }
}