tree/test/Tree_Diameter.test.cpp

• View this file on GitHub
• Last update: 2023-07-25 00:50:50+07:00
• Problem: https://judge.yosupo.jp/problem/tree_diameter

Depends on

• Tree Diameter (tree/tree_diameter.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/tree_diameter"

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#include "../tree_diameter.hpp"

void solve(int ith) {
  int n;
  cin >> n;
  vector<vector<pair<int, int>>> tree(n);
  for(int i = 0; i < n - 1; ++i){
    int u, v, w;
    cin >> u >> v >> w;
    tree[u].emplace_back(v, w);
    tree[v].emplace_back(u, w);
  }
  auto [diameter, path] = get_diameter(tree);
  cout << diameter << ' ' << path.size() << '\n';
  for(auto v: path) cout << v << ' ';
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cin.exceptions(cin.failbit);
  int tc = 1;
  // cin >> tc;
  for (int i = 1; i <= tc; ++i) solve(i);
}

#line 1 "tree/test/Tree_Diameter.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/tree_diameter"

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#line 1 "tree/tree_diameter.hpp"
pair<ll, vector<int>> get_diameter(const vector<vector<pair<int, int>>>& g) {
  int n = g.size();
  vector<ll> dist(n);
  vector<int> parent(n);

  auto dfs = [&](auto self, int u, int fu, ll cur_dist) -> void {
    dist[u] = cur_dist;
    parent[u] = fu;
    for (auto [v, cost] : g[u])
      if (v != fu) {
        self(self, v, u, cur_dist + cost);
      }
  };
  dfs(dfs, 0, -1, 0);
  // r = furthest node from root
  int r = max_element(dist.begin(), dist.end()) - dist.begin();
  dfs(dfs, r, -1, 0);
  // r->s = longest path
  int s = max_element(dist.begin(), dist.end()) - dist.begin();

  vector<int> path;
  for (int x = s; x >= 0; x = parent[x]) path.push_back(x);

  return {dist[s], path};
}
#line 10 "tree/test/Tree_Diameter.test.cpp"

void solve(int ith) {
  int n;
  cin >> n;
  vector<vector<pair<int, int>>> tree(n);
  for(int i = 0; i < n - 1; ++i){
    int u, v, w;
    cin >> u >> v >> w;
    tree[u].emplace_back(v, w);
    tree[v].emplace_back(u, w);
  }
  auto [diameter, path] = get_diameter(tree);
  cout << diameter << ' ' << path.size() << '\n';
  for(auto v: path) cout << v << ' ';
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cin.exceptions(cin.failbit);
  int tc = 1;
  // cin >> tc;
  for (int i = 1; i <= tc; ++i) solve(i);
}

Back to top page