ABC070: D - Transit Tree Path
問題
解説
与えられたグラフは木なので、2頂点間のパスは最短距離になる。 必ずを通るので、まずを起点としてDFSしてからの距離を計算しておいて、各クエリについてを求めればよい。
余談:はじめが与えられていないと思って考えてしまった。その場合は適当に選んだ頂点に対して同様に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"; } }