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

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

問題へのリンク

問題概要

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

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

制約

• 
• 

考えたこと

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

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

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

• から への最短経路長
• から への最短経路長

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

• DFS
• ツリー DP
• Dijkstra 法

なんでもござれという感じ。ここではツリー上を 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;
    }
}