This documentation is automatically generated by online-judge-tools/verification-helper
#include "graph/tree_diameter.hpp"tree_diameter<T> d(n): 頂点数 n、辺の重みの型 T。add_edge(u, v, w = 1): 重み w の辺 $(u, v)$ を追加する。build(): 構築する。length(): 直径の長さを返す。ends(): 直径の両端 (u, v) を返す。path(): u から v への直径の頂点列を返す。center(): 直径の中点を返す。頂点 c にあれば (c, c)、辺 $(a, b)$ の内部にあれば (a, b)。build: $\mathcal{O}(N)$#pragma once
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
template <class T>
struct tree_diameter {
public:
tree_diameter() : tree_diameter(0) {
}
explicit tree_diameter(int n) : _n(n), g(n) {
}
void add_edge(int u, int v, T w = 1) {
assert(0 <= u && u < _n);
assert(0 <= v && v < _n);
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
void build() {
assert(_n >= 1);
std::vector<int> par;
std::vector<T> d;
search(0, d, par);
_u = int(std::ranges::max_element(d) - d.begin());
search(_u, d, par);
_v = int(std::ranges::max_element(d) - d.begin());
_length = d[_v];
_path.clear();
for (int x = _v; x != -1; x = par[x]) _path.push_back(x);
std::ranges::reverse(_path);
for (int i = 0;; i++) {
T pos = d[_path[i]];
if (pos == _length - pos) {
_center = {_path[i], _path[i]};
break;
}
if (pos > _length - pos) {
_center = {_path[i - 1], _path[i]};
break;
}
}
}
T length() const {
return _length;
}
std::pair<int, int> ends() const {
return {_u, _v};
}
const std::vector<int>& path() const {
return _path;
}
std::pair<int, int> center() const {
return _center;
}
private:
int _n, _u = -1, _v = -1;
std::pair<int, int> _center = {-1, -1};
T _length = T(0);
std::vector<std::vector<std::pair<int, T>>> g;
std::vector<int> _path;
void search(int s, std::vector<T>& d, std::vector<int>& par) const {
d.assign(_n, T(0));
par.assign(_n, -1);
std::vector<int> st = {s};
par[s] = s;
while (!st.empty()) {
int x = st.back();
st.pop_back();
for (auto [y, w] : g[x]) {
if (par[y] != -1) continue;
par[y] = x;
d[y] = d[x] + w;
st.push_back(y);
}
}
par[s] = -1;
}
};#line 2 "graph/tree_diameter.hpp"
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
template <class T>
struct tree_diameter {
public:
tree_diameter() : tree_diameter(0) {
}
explicit tree_diameter(int n) : _n(n), g(n) {
}
void add_edge(int u, int v, T w = 1) {
assert(0 <= u && u < _n);
assert(0 <= v && v < _n);
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
void build() {
assert(_n >= 1);
std::vector<int> par;
std::vector<T> d;
search(0, d, par);
_u = int(std::ranges::max_element(d) - d.begin());
search(_u, d, par);
_v = int(std::ranges::max_element(d) - d.begin());
_length = d[_v];
_path.clear();
for (int x = _v; x != -1; x = par[x]) _path.push_back(x);
std::ranges::reverse(_path);
for (int i = 0;; i++) {
T pos = d[_path[i]];
if (pos == _length - pos) {
_center = {_path[i], _path[i]};
break;
}
if (pos > _length - pos) {
_center = {_path[i - 1], _path[i]};
break;
}
}
}
T length() const {
return _length;
}
std::pair<int, int> ends() const {
return {_u, _v};
}
const std::vector<int>& path() const {
return _path;
}
std::pair<int, int> center() const {
return _center;
}
private:
int _n, _u = -1, _v = -1;
std::pair<int, int> _center = {-1, -1};
T _length = T(0);
std::vector<std::vector<std::pair<int, T>>> g;
std::vector<int> _path;
void search(int s, std::vector<T>& d, std::vector<int>& par) const {
d.assign(_n, T(0));
par.assign(_n, -1);
std::vector<int> st = {s};
par[s] = s;
while (!st.empty()) {
int x = st.back();
st.pop_back();
for (auto [y, w] : g[x]) {
if (par[y] != -1) continue;
par[y] = x;
d[y] = d[x] + w;
st.push_back(y);
}
}
par[s] = -1;
}
};