tree_diameter.hpp¶
无权树返回直径端点和各点最远距离；带权树用一次树形 DP 返回最大路径，支持负边和零边路径。直径 monoid 仍要求非负树度量，规范端点平局以保证结合律；使用前绑定存活的共享 LCA 上下文。
Complexity: Time: \(O(n)\) for a tree diameter; \(O(1)\) diameter-monoid merge. Space: \(O(n)\), including \(O(n)\) recursive depth for the weighted path DP.
AC 记录：tree_diameter。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n) for a tree diameter; O(1) diameter-monoid merge.
/// Space: O(n), including O(n) recursive depth for the weighted path DP.
#include "noya/graph/lowest_common_ancestor.hpp"
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <limits>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
/// @brief Unweighted tree diameter, endpoints and every vertex's eccentricity.
/// Input must be an undirected tree with valid endpoints, or empty; vertex
/// count must fit int. Input is unchanged. Each farthest endpoint is the lowest
/// vertex ID among ties, starting the first scan at 0. Empty input returns
/// (-1,-1,-1,{}). Three BFS passes store distances without predecessor arrays.
inline std::tuple<int, int, int, std::vector<int>>
tree_diam(std::vector<std::vector<int>> &g) {
assert(g.size() <= std::size_t(std::numeric_limits<int>::max()));
if (g.empty()) return {-1, -1, -1, {}};
auto bfs = [&](int start) {
std::vector<int> distance(g.size(), -1), queue{start};
distance[start] = 0;
for (int i = 0; i < int(queue.size()); ++i) {
int u = queue[i];
for (int v : g[u]) if (distance[v] == -1) {
distance[v] = distance[u] + 1;
queue.push_back(v);
}
}
return distance;
};
auto distance = bfs(0);
int a = int(std::max_element(distance.begin(), distance.end()) - distance.begin());
distance = bfs(a);
int b = int(std::max_element(distance.begin(), distance.end()) - distance.begin());
int diameter = distance[b];
auto other = bfs(b);
for (std::size_t u = 0; u < g.size(); ++u)
distance[u] = std::max(distance[u], other[u]);
return {diameter, a, b, std::move(distance)};
}
/// @brief Maximum-weight simple path in an undirected tree, including a
/// zero-edge path. Signed negative edges are supported. Empty input returns
/// (0,{}); all-nonpositive trees return (0,{0}). Input is unchanged; vertex
/// count must fit int and endpoints must be valid.
/// Weights and the maximum path sum must be representable by Weight. Floating
/// weights must be finite and are subject to ordinary rounding. Any maximum
/// path is allowed; ties follow DFS adjacency order. Recursive depth is O(n).
template <class Weight>
std::pair<Weight, std::vector<int>> weighted_tree_diameter(
const std::vector<std::vector<std::pair<int, Weight>>> &G) {
assert(G.size() <= std::size_t(std::numeric_limits<int>::max()));
if (G.empty()) return {Weight{}, {}};
std::vector<int> parent(G.size(), -1);
Weight answer{};
int a = 0, b = 0, center = 0;
auto dfs = [&](auto &self, int u, int from) -> std::pair<Weight, int> {
std::pair<Weight, int> down{Weight{}, u};
for (const auto &[v, weight] : G[u]) if (v != from) {
parent[v] = u;
auto [length, endpoint] = self(self, v, u);
length = length + weight;
Weight candidate = down.first + length;
if (answer < candidate) {
answer = candidate;
a = down.second;
b = endpoint;
center = u;
}
if (down.first < length) down = {length, endpoint};
}
return down;
};
dfs(dfs, 0, -1);
std::vector<int> path;
for (int u = a; u != center; u = parent[u]) path.push_back(u);
path.push_back(center);
auto pivot = path.size();
for (int u = b; u != center; u = parent[u]) path.push_back(u);
std::reverse(path.begin() + pivot, path.end());
return {answer, std::move(path)};
}
/// @brief Diameter monoid for vertex subsets in a nonnegative tree metric.
/// Requires one live fastlca context; set_lca replaces the shared context for
/// all instances. LCA distances must fit int64_t. Negative edge weights are
/// unsupported here, unlike weighted_tree_diameter's explicit path DP.
/// Endpoints are sorted; among tied lengths choose the lexicographically largest
/// endpoint pair. Canonical states from make/op and unit form a commutative
/// monoid. Oriented input witnesses are normalized before merging.
struct diameter_monoid {
using value_type = std::pair<int64_t, std::array<int, 2>>;
using S = value_type;
using X = value_type;
static constexpr value_type identity = {-1, {-1, -1}};
static constexpr bool commute = true;
diameter_monoid() = default;
explicit diameter_monoid(const fastlca &l) { set_lca(l); }
static const fastlca *&get_lca() {
static const fastlca *lca = nullptr;
return lca;
}
static void set_lca(const fastlca &l) { get_lca() = &l; }
static value_type unit() { return identity; }
static value_type e() { return unit(); }
static value_type make(int v) { return {0, {v, v}}; }
static value_type from_vertex(int v) { return make(v); }
static value_type op(value_type a, value_type b) {
if (a.second[0] > a.second[1]) std::swap(a.second[0], a.second[1]);
if (b.second[0] > b.second[1]) std::swap(b.second[0], b.second[1]);
if (a == unit()) return b;
if (b == unit()) return a;
const fastlca *lca = get_lca();
assert(lca != nullptr);
value_type c = std::max(a, b);
int na = 1 + (a.second[0] != a.second[1]);
int nb = 1 + (b.second[0] != b.second[1]);
for (int i = 0; i < na; ++i)
for (int j = 0; j < nb; ++j) {
int x = a.second[i], y = b.second[j];
int64_t distance = lca->distance(x, y);
if (distance < c.first) continue;
if (x > y) std::swap(x, y);
std::array<int, 2> endpoints{x, y};
if (distance > c.first || c.second < endpoints) c = {distance, endpoints};
}
return c;
}
static value_type merge(value_type a, value_type b) { return op(a, b); }
};
} // namespace noya
// NOYA_TREE_DIAMETER_HPP
#ifndef NOYA_TREE_DIAMETER_HPP
#define NOYA_TREE_DIAMETER_HPP 1
/// @complexity Time: O(n) for a tree diameter; O(1) diameter-monoid merge.
/// Space: O(n), including O(n) recursive depth for the weighted path DP.
#include "noya/graph/lowest_common_ancestor.hpp"
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <limits>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
/// @brief Unweighted tree diameter, endpoints and every vertex's eccentricity.
/// Input must be an undirected tree with valid endpoints, or empty; vertex
/// count must fit int. Input is unchanged. Each farthest endpoint is the lowest
/// vertex ID among ties, starting the first scan at 0. Empty input returns
/// (-1,-1,-1,{}). Three BFS passes store distances without predecessor arrays.
inline std::tuple<int, int, int, std::vector<int>>
tree_diam(std::vector<std::vector<int>> &g) {
assert(g.size() <= std::size_t(std::numeric_limits<int>::max()));
if (g.empty()) return {-1, -1, -1, {}};
auto bfs = [&](int start) {
std::vector<int> distance(g.size(), -1), queue{start};
distance[start] = 0;
for (int i = 0; i < int(queue.size()); ++i) {
int u = queue[i];
for (int v : g[u]) if (distance[v] == -1) {
distance[v] = distance[u] + 1;
queue.push_back(v);
}
}
return distance;
};
auto distance = bfs(0);
int a = int(std::max_element(distance.begin(), distance.end()) - distance.begin());
distance = bfs(a);
int b = int(std::max_element(distance.begin(), distance.end()) - distance.begin());
int diameter = distance[b];
auto other = bfs(b);
for (std::size_t u = 0; u < g.size(); ++u)
distance[u] = std::max(distance[u], other[u]);
return {diameter, a, b, std::move(distance)};
}
/// @brief Maximum-weight simple path in an undirected tree, including a
/// zero-edge path. Signed negative edges are supported. Empty input returns
/// (0,{}); all-nonpositive trees return (0,{0}). Input is unchanged; vertex
/// count must fit int and endpoints must be valid.
/// Weights and the maximum path sum must be representable by Weight. Floating
/// weights must be finite and are subject to ordinary rounding. Any maximum
/// path is allowed; ties follow DFS adjacency order. Recursive depth is O(n).
template <class Weight>
std::pair<Weight, std::vector<int>> weighted_tree_diameter(
const std::vector<std::vector<std::pair<int, Weight>>> &G) {
assert(G.size() <= std::size_t(std::numeric_limits<int>::max()));
if (G.empty()) return {Weight{}, {}};
std::vector<int> parent(G.size(), -1);
Weight answer{};
int a = 0, b = 0, center = 0;
auto dfs = [&](auto &self, int u, int from) -> std::pair<Weight, int> {
std::pair<Weight, int> down{Weight{}, u};
for (const auto &[v, weight] : G[u]) if (v != from) {
parent[v] = u;
auto [length, endpoint] = self(self, v, u);
length = length + weight;
Weight candidate = down.first + length;
if (answer < candidate) {
answer = candidate;
a = down.second;
b = endpoint;
center = u;
}
if (down.first < length) down = {length, endpoint};
}
return down;
};
dfs(dfs, 0, -1);
std::vector<int> path;
for (int u = a; u != center; u = parent[u]) path.push_back(u);
path.push_back(center);
auto pivot = path.size();
for (int u = b; u != center; u = parent[u]) path.push_back(u);
std::reverse(path.begin() + pivot, path.end());
return {answer, std::move(path)};
}
/// @brief Diameter monoid for vertex subsets in a nonnegative tree metric.
/// Requires one live fastlca context; set_lca replaces the shared context for
/// all instances. LCA distances must fit int64_t. Negative edge weights are
/// unsupported here, unlike weighted_tree_diameter's explicit path DP.
/// Endpoints are sorted; among tied lengths choose the lexicographically largest
/// endpoint pair. Canonical states from make/op and unit form a commutative
/// monoid. Oriented input witnesses are normalized before merging.
struct diameter_monoid {
using value_type = std::pair<int64_t, std::array<int, 2>>;
using S = value_type;
using X = value_type;
static constexpr value_type identity = {-1, {-1, -1}};
static constexpr bool commute = true;
diameter_monoid() = default;
explicit diameter_monoid(const fastlca &l) { set_lca(l); }
static const fastlca *&get_lca() {
static const fastlca *lca = nullptr;
return lca;
}
static void set_lca(const fastlca &l) { get_lca() = &l; }
static value_type unit() { return identity; }
static value_type e() { return unit(); }
static value_type make(int v) { return {0, {v, v}}; }
static value_type from_vertex(int v) { return make(v); }
static value_type op(value_type a, value_type b) {
if (a.second[0] > a.second[1]) std::swap(a.second[0], a.second[1]);
if (b.second[0] > b.second[1]) std::swap(b.second[0], b.second[1]);
if (a == unit()) return b;
if (b == unit()) return a;
const fastlca *lca = get_lca();
assert(lca != nullptr);
value_type c = std::max(a, b);
int na = 1 + (a.second[0] != a.second[1]);
int nb = 1 + (b.second[0] != b.second[1]);
for (int i = 0; i < na; ++i)
for (int j = 0; j < nb; ++j) {
int x = a.second[i], y = b.second[j];
int64_t distance = lca->distance(x, y);
if (distance < c.first) continue;
if (x > y) std::swap(x, y);
std::array<int, 2> endpoints{x, y};
if (distance > c.first || c.second < endpoints) c = {distance, endpoints};
}
return c;
}
static value_type merge(value_type a, value_type b) { return op(a, b); }
};
} // namespace noya
#endif // NOYA_TREE_DIAMETER_HPP
/// @complexity Time: O(n) for a tree diameter; O(1) diameter-monoid merge.
/// Space: O(n), including O(n) recursive depth for the weighted path DP.
/// @complexity Time: O(n log n) build, O(1) LCA/distance/ancestor checks.
/// Space: O(n log n). Path listing is linear in the returned path length.
/// @complexity Time: O(n log n) build and O(1) idempotent range query.
/// Space: O(n log n).
#include <bit>
#include <cassert>
#include <utility>
#include <vector>
namespace noya {
/// @brief Static O(1) range product for an idempotent monoid.
/// Monoid provides value_type, unit(), and an associative, idempotent op().
/// Empty ranges return unit(); input arrays are owned by the table.
/// @details For k = floor(log2(r-l)), [l, r) is covered by the length-2^k
/// blocks beginning at l and ending at r. They may overlap, so combining them
/// is correct precisely because op(x, x) = x.
template <class Monoid> class sparse_table {
public:
using value_type = typename Monoid::value_type;
sparse_table() = default;
explicit sparse_table(std::vector<value_type> a) { build(std::move(a)); }
template <class F> sparse_table(int n_, F f) { build(n_, std::move(f)); }
template <class F> void build(int n_, F f) {
assert(n_ >= 0);
std::vector<value_type> a;
a.reserve(n_);
for (int i = 0; i < n_; i++) {
a.push_back(f(i));
}
build(std::move(a));
}
/// @brief Rebuild from a static array.
void build(std::vector<value_type> a) {
n = int(a.size());
int lg = int(std::bit_width(static_cast<unsigned>(n)));
st.resize(lg);
if (n == 0) {
return;
}
st[0] = std::move(a);
for (int dep = 1; dep < lg; dep++) {
int w = 1 << dep;
int hf = w >> 1;
int len = n - w + 1;
st[dep].resize(len, Monoid::unit());
for (int l = 0; l < len; l++) {
st[dep][l] = Monoid::op(st[dep - 1][l], st[dep - 1][l + hf]);
}
}
}
int size() const { return n; }
bool empty() const { return n == 0; }
value_type get(int p) const {
assert(0 <= p && p < n);
return st[0][p];
}
value_type all_prod() const { return prod(0, n); }
/// @brief Return the idempotent product over [l, r).
value_type prod(int l, int r) const {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return Monoid::unit();
}
int dep = int(std::bit_width(static_cast<unsigned>(r - l))) - 1;
int w = 1 << dep;
return Monoid::op(st[dep][l], st[dep][r - w]);
}
private:
int n = 0;
std::vector<std::vector<value_type>> st;
};
} // namespace noya
/// @complexity Time: O(n) build; common queries add O(1) work to their LCA calls,
/// except path(), which takes O(path length). Space: O(n).
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>
namespace noya {
/// @brief Recursive rooted-tree preprocessing shared by RMQ LCA and HLD.
/// The graph is a connected tree, with integer endpoints or (endpoint, weight)
/// pairs. Root depth is zero, root parent is -1, and subtree ranges are [l, r).
/// n must fit int. DFS preorder follows each adjacency list's original order.
/// No adjacency-list copy, RMQ table, jump table, or heavy paths are retained.
struct tree_preprocessing {
int n = 0;
int rt = -1;
std::vector<int> fa, d, dfn, siz, tl;
tree_preprocessing() = default;
template <class Edge>
explicit tree_preprocessing(const std::vector<std::vector<Edge>> &g,
int root = 0) {
build(g, root);
}
template <class Edge> static int endpoint(const Edge &edge) {
if constexpr (std::is_integral_v<Edge>) {
return int(edge);
} else {
return int(std::get<0>(edge));
}
}
template <class Edge>
void build(const std::vector<std::vector<Edge>> &g, int root = 0) {
n = int(g.size());
rt = n == 0 ? -1 : root;
fa.assign(n, -1);
d.assign(n, 0);
dfn.assign(n, -1);
siz.assign(n, 1);
tl.clear();
tl.reserve(n);
if (n == 0) {
return;
}
assert(0 <= root && root < n);
auto dfs = [&](auto &self, int u) -> void {
assert(dfn[u] == -1);
dfn[u] = int(tl.size());
tl.push_back(u);
for (const auto &edge : g[u]) {
int v = endpoint(edge);
assert(0 <= v && v < n);
if (v != fa[u]) {
fa[v] = u;
d[v] = d[u] + 1;
self(self, v);
siz[u] += siz[v];
}
}
};
dfs(dfs, root);
assert(int(tl.size()) == n);
}
void build(const std::vector<std::vector<int>> &g = {}, int root = 0) {
build<int>(g, root);
}
/// True when a is in b's subtree (including a == b).
bool is_subtree(int a, int b) const {
assert(0 <= a && a < n && 0 <= b && b < n);
return dfn[b] <= dfn[a] && dfn[a] < dfn[b] + siz[b];
}
std::array<int, 2> subtree(int u) const {
assert(0 <= u && u < n);
return {dfn[u], dfn[u] + siz[u]};
}
};
/// @brief Shared tree queries with compile-time dispatch to Derived::lca().
template <class Derived> struct tree_queries : tree_preprocessing {
int rooted_lca(int a, int b, int root) const {
const auto &self = static_cast<const Derived &>(*this);
return self.lca(a, b) ^ self.lca(a, root) ^ self.lca(b, root);
}
std::int64_t distance(int a, int b) const {
const auto &self = static_cast<const Derived &>(*this);
int c = self.lca(a, b);
return std::int64_t(d[a]) + d[b] - 2 * std::int64_t(d[c]);
}
/// Intersection of paths a->b and c->e, oriented along c->e.
/// Empty returns {-1,-1}; a single shared vertex is returned twice.
std::pair<int, int> intersection(int a, int b, int c, int e) const {
const auto &self = static_cast<const Derived &>(*this);
int ab = self.lca(a, b), ac = self.lca(a, c), ae = self.lca(a, e);
int bc = self.lca(b, c), be = self.lca(b, e), ce = self.lca(c, e);
int x = ab ^ ac ^ bc;
int y = ab ^ ae ^ be;
if (x != y) {
return {x, y};
}
int z = ac ^ ae ^ ce;
return x == z ? std::pair{x, x} : std::pair{-1, -1};
}
std::pair<int, int> intersection(std::pair<int, int> a,
std::pair<int, int> b) const {
return intersection(a.first, a.second, b.first, b.second);
}
/// List every vertex from a to b, including both endpoints, in one buffer.
std::vector<int> path(int a, int b) const {
assert(0 <= a && a < n && 0 <= b && b < n);
if (a == b) {
return {a};
}
const auto &self = static_cast<const Derived &>(*this);
int c = self.lca(a, b);
std::vector<int> result;
result.reserve((d[a] - d[c]) + (d[b] - d[c]) + 1);
while (a != c) {
result.push_back(a);
a = fa[a];
}
result.push_back(c);
auto pivot = result.size();
while (b != c) {
result.push_back(b);
b = fa[b];
}
std::reverse(result.begin() + pivot, result.end());
return result;
}
};
} // namespace noya
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <utility>
#include <vector>
namespace noya {
/// @brief RMQ LCA with O(1) queries, without heavy paths or a binary jump table.
/// RMQ stores only parent DFS indices; tl maps the minimum back to a vertex.
/// Weighted adjacency automatically enables weighted distance; rebuilding from
/// unweighted adjacency resets it. Use hld for kth_ancestor/kth_on_path queries.
/// Weights must be integers (including signed/unsigned __int128). Each weight,
/// root distance, and returned distance must be representable as int64_t.
struct fastlca : tree_queries<fastlca> {
struct minimum_index_semilattice {
using value_type = int;
static value_type unit() { return std::numeric_limits<int>::max(); }
static value_type op(value_type a, value_type b) { return std::min(a, b); }
};
sparse_table<minimum_index_semilattice> ST;
std::vector<std::int64_t> len;
bool wt = false;
fastlca() = default;
template <class Edge>
explicit fastlca(const std::vector<std::vector<Edge>> &g, int root = 0) {
build(g, root);
}
template <class Edge>
void build(const std::vector<std::vector<Edge>> &g, int root = 0) {
tree_preprocessing::build(g, root);
std::vector<int> rmq(n);
for (int u : tl) {
rmq[dfn[u]] = fa[u] == -1 ? -1 : dfn[fa[u]];
}
ST.build(std::move(rmq));
wt = !std::is_integral_v<Edge>;
len.clear();
if constexpr (!std::is_integral_v<Edge>) {
using Weight = std::remove_cvref_t<decltype(std::get<1>(std::declval<Edge>()))>;
static_assert(std::numeric_limits<Weight>::is_integer,
"fastlca requires integer edge weights");
static_assert(sizeof(Weight) <= sizeof(__int128),
"fastlca supports integer weights up to 128 bits");
len.assign(n, 0);
for (int u : tl) {
for (const auto &edge : g[u]) {
int v = endpoint(edge);
if (fa[v] == u) {
const auto weight = std::get<1>(edge);
if constexpr (std::numeric_limits<Weight>::is_signed) {
assert(__int128(weight) >= std::numeric_limits<std::int64_t>::lowest() &&
__int128(weight) <= std::numeric_limits<std::int64_t>::max());
} else {
assert(__uint128_t(weight) <=
__uint128_t(std::numeric_limits<std::int64_t>::max()));
}
__int128 value = __int128(len[u]) + __int128(weight);
assert(std::numeric_limits<std::int64_t>::lowest() <= value &&
value <= std::numeric_limits<std::int64_t>::max());
len[v] = std::int64_t(value);
}
}
}
}
}
void build(const std::vector<std::vector<int>> &g = {}, int root = 0) {
build<int>(g, root);
}
int lca(int u, int v) const {
assert(0 <= u && u < n && 0 <= v && v < n);
if (u == v) {
return u;
}
int a = dfn[u], b = dfn[v];
if (a > b) {
std::swap(a, b);
}
return tl[ST.prod(a + 1, b + 1)];
}
std::int64_t distance(int a, int b) const {
if (!wt) {
return tree_queries<fastlca>::distance(a, b);
}
int c = lca(a, b);
__int128 value = __int128(len[a]) + len[b] - 2 * __int128(len[c]);
assert(std::numeric_limits<std::int64_t>::lowest() <= value &&
value <= std::numeric_limits<std::int64_t>::max());
return std::int64_t(value);
}
};
} // namespace noya
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <limits>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
/// @brief Unweighted tree diameter, endpoints and every vertex's eccentricity.
/// Input must be an undirected tree with valid endpoints, or empty; vertex
/// count must fit int. Input is unchanged. Each farthest endpoint is the lowest
/// vertex ID among ties, starting the first scan at 0. Empty input returns
/// (-1,-1,-1,{}). Three BFS passes store distances without predecessor arrays.
inline std::tuple<int, int, int, std::vector<int>>
tree_diam(std::vector<std::vector<int>> &g) {
assert(g.size() <= std::size_t(std::numeric_limits<int>::max()));
if (g.empty()) return {-1, -1, -1, {}};
auto bfs = [&](int start) {
std::vector<int> distance(g.size(), -1), queue{start};
distance[start] = 0;
for (int i = 0; i < int(queue.size()); ++i) {
int u = queue[i];
for (int v : g[u]) if (distance[v] == -1) {
distance[v] = distance[u] + 1;
queue.push_back(v);
}
}
return distance;
};
auto distance = bfs(0);
int a = int(std::max_element(distance.begin(), distance.end()) - distance.begin());
distance = bfs(a);
int b = int(std::max_element(distance.begin(), distance.end()) - distance.begin());
int diameter = distance[b];
auto other = bfs(b);
for (std::size_t u = 0; u < g.size(); ++u)
distance[u] = std::max(distance[u], other[u]);
return {diameter, a, b, std::move(distance)};
}
/// @brief Maximum-weight simple path in an undirected tree, including a
/// zero-edge path. Signed negative edges are supported. Empty input returns
/// (0,{}); all-nonpositive trees return (0,{0}). Input is unchanged; vertex
/// count must fit int and endpoints must be valid.
/// Weights and the maximum path sum must be representable by Weight. Floating
/// weights must be finite and are subject to ordinary rounding. Any maximum
/// path is allowed; ties follow DFS adjacency order. Recursive depth is O(n).
template <class Weight>
std::pair<Weight, std::vector<int>> weighted_tree_diameter(
const std::vector<std::vector<std::pair<int, Weight>>> &G) {
assert(G.size() <= std::size_t(std::numeric_limits<int>::max()));
if (G.empty()) return {Weight{}, {}};
std::vector<int> parent(G.size(), -1);
Weight answer{};
int a = 0, b = 0, center = 0;
auto dfs = [&](auto &self, int u, int from) -> std::pair<Weight, int> {
std::pair<Weight, int> down{Weight{}, u};
for (const auto &[v, weight] : G[u]) if (v != from) {
parent[v] = u;
auto [length, endpoint] = self(self, v, u);
length = length + weight;
Weight candidate = down.first + length;
if (answer < candidate) {
answer = candidate;
a = down.second;
b = endpoint;
center = u;
}
if (down.first < length) down = {length, endpoint};
}
return down;
};
dfs(dfs, 0, -1);
std::vector<int> path;
for (int u = a; u != center; u = parent[u]) path.push_back(u);
path.push_back(center);
auto pivot = path.size();
for (int u = b; u != center; u = parent[u]) path.push_back(u);
std::reverse(path.begin() + pivot, path.end());
return {answer, std::move(path)};
}
/// @brief Diameter monoid for vertex subsets in a nonnegative tree metric.
/// Requires one live fastlca context; set_lca replaces the shared context for
/// all instances. LCA distances must fit int64_t. Negative edge weights are
/// unsupported here, unlike weighted_tree_diameter's explicit path DP.
/// Endpoints are sorted; among tied lengths choose the lexicographically largest
/// endpoint pair. Canonical states from make/op and unit form a commutative
/// monoid. Oriented input witnesses are normalized before merging.
struct diameter_monoid {
using value_type = std::pair<int64_t, std::array<int, 2>>;
using S = value_type;
using X = value_type;
static constexpr value_type identity = {-1, {-1, -1}};
static constexpr bool commute = true;
diameter_monoid() = default;
explicit diameter_monoid(const fastlca &l) { set_lca(l); }
static const fastlca *&get_lca() {
static const fastlca *lca = nullptr;
return lca;
}
static void set_lca(const fastlca &l) { get_lca() = &l; }
static value_type unit() { return identity; }
static value_type e() { return unit(); }
static value_type make(int v) { return {0, {v, v}}; }
static value_type from_vertex(int v) { return make(v); }
static value_type op(value_type a, value_type b) {
if (a.second[0] > a.second[1]) std::swap(a.second[0], a.second[1]);
if (b.second[0] > b.second[1]) std::swap(b.second[0], b.second[1]);
if (a == unit()) return b;
if (b == unit()) return a;
const fastlca *lca = get_lca();
assert(lca != nullptr);
value_type c = std::max(a, b);
int na = 1 + (a.second[0] != a.second[1]);
int nb = 1 + (b.second[0] != b.second[1]);
for (int i = 0; i < na; ++i)
for (int j = 0; j < nb; ++j) {
int x = a.second[i], y = b.second[j];
int64_t distance = lca->distance(x, y);
if (distance < c.first) continue;
if (x > y) std::swap(x, y);
std::array<int, 2> endpoints{x, y};
if (distance > c.first || c.second < endpoints) c = {distance, endpoints};
}
return c;
}
static value_type merge(value_type a, value_type b) { return op(a, b); }
};
} // namespace noya
// NOYA_TREE_DIAMETER_HPP