H - 最短経路/Shortest Path Editorial by Nyaan


まずは 問題を簡単にして、 \(i\) を固定した場合を考えてみましょう。
\(i\) を始点とする深さ優先探索 (DFS) を行うことで、全ての \(j\) に対して \(i - j\) 間の距離を \(\mathrm{O}(N)\) で求めることができることが知られています。
よって、深さ優先探索で 全ての距離を列挙したあとに 距離が \(X\) であるような頂点対が存在するかを調べれば \(\mathrm{O}(N)\) でこの問題を解くことができます。

元の問題も上記のアルゴリズムを利用すれば解くことができます。
すなわち、全ての \(i\)に対して \(i\) を始点とする DFS を行えば、 \(\mathrm{O}(N)\) の操作を \(N\) 回行って全ての頂点対に対して長さが \(X\) のものが存在するか判定することができます。計算量は \(\mathrm{O}(N \times N) = \mathrm{O}(N^2)\) となり、与えられた制約内では十分高速に解くことができます。

C++ での実装例を以下に載せます。

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

using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)

ll N, X;
vector<vector<pair<ll, ll>>> g;
bool ok = false;

void dfs(int c, int p, ll len) {
  if (len == X) ok = true;
  for (auto& [d, w] : g[c]) {
    if (d == p) continue;
    dfs(d, c, len + w);
  }
}

int main() {
  cin >> N >> X;
  g.resize(N);
  rep(i, N - 1) {
    ll a, b, c;
    cin >> a >> b >> c;
    --a, --b;
    g[a].emplace_back(b, c);
    g[b].emplace_back(a, c);
  }
  rep(i, N) dfs(i, -1, 0);
  cout << (ok ? "Yes" : "No") << "\n";
}

posted:
last update: