제출 #1182171

#제출 시각아이디문제언어결과실행 시간메모리
1182171avighnaDesignated Cities (JOI19_designated_cities)C++20
0 / 100
121 ms32928 KiB
#include <bits/stdc++.h>

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n;
  std::cin >> n;
  std::vector<std::vector<std::pair<int, std::pair<long long, long long>>>> adj(
      n + 1);
  long long tot = 0;
  for (int i = 0, a, b, c, d; i < n - 1; ++i) {
    std::cin >> a >> b >> c >> d;
    adj[a].push_back({b, {c, d}});
    adj[b].push_back({a, {d, c}});
    tot += c + d;
  }

  std::vector<std::vector<std::pair<int, long long>>> adj2(n + 1);
  long long up = 0;
  auto dfs = [&](auto &&self, int u, int p) -> void {
    for (auto &[i, pr] : adj[u]) {
      if (i == p) {
        continue;
      }
      auto [c, d] = pr;
      up += d;
      adj2[u].push_back({i, c});
      adj2[i].push_back({u, c});
      self(self, i, u);
    }
  };
  dfs(dfs, 1, 0);

  auto diameter =
      [&](int n, std::vector<std::vector<std::pair<int, long long>>> &adj) {
        std::pair<long long, long long> pr = {0, 1};
        auto dfs = [&](auto &&self, int u, int p, int d) -> void {
          for (auto &[i, wt] : adj[u]) {
            if (i == p) {
              continue;
            }
            if (d + wt > pr.first) {
              pr.first = d + wt;
              pr.second = i;
            }
            self(self, i, u, d + wt);
          }
        };
        dfs(dfs, 1, 0, 0);
        int u = pr.second;
        pr = {0, u};
        dfs(dfs, u, 0, 0);
        return pr.first;
      };

  long long ans = up + diameter(n, adj2);

  int q;
  std::cin >> q;
  while (q--) {
    int x;
    std::cout << tot - ans << '\n';
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...