木構造の最短経路問題 ABC-70D Transit Tree Path

問題文

頂点の木が与えられます。
木とはグラフの一種であり、頂点の数をとすると、辺の数がN-1本である閉路の無い連結グラフです。
番目の辺は頂点と頂点を距離で結びます。
また、Q個の質問クエリと整数が与えらえます。
番目の質問クエリでは、頂点から頂点を経由しつつ、頂点まで移動する場合の最短経路の距離を求めて下さい。
atcoder.jp

考えたこと

1. 頂点から頂点への頂点を経由する場合の最短経路は、頂点からへの最短経路と頂点からへの最短経路の和で求まる。
2. 最初ダイクストラ法で実装しようとしたが、よく考えたら、閉路が無い木構造であり、ある頂点からある頂点までの経路が一つしかないため、深さ優先探索(dfs)で探索すれば十分であることが分かった。
3. 辺の数がなので、間違えてforループを回すとバグらせるので注意が必要。

const int limit = 100010;
using edge = struct{ll to; ll cost;};
vector<edge> tree[limit];
ll depth[limit];


void dfs(ll v, ll p, ll d){
    depth[v] = d;
    for(auto &e : tree[v]){
        if(e.to == p) continue;
        dfs(e.to, v, d+e.cost);
    }
}

int main() {
    ll n; cin >> n;
    for(ll i=0; i<n-1; i++){
        ll a, b, c; cin >> a >> b >> c;
        tree[a].push_back({b, c});
        tree[b].push_back({a, c});
    }

    ll Q, K; cin >> Q >> K;
    dfs(K, -1, 0);

    for(ll i=0; i<Q; i++){
        ll x, y; cin >> x >> y;
        cout << depth[x]+depth[y] << '\n';
    }


    return 0;
}