This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <vector>
#include "graph/tree_diameter.hpp"
int main() {
std::mt19937 rng(20261028);
for (int trial = 0; trial < 300; trial++) {
int n = 1 + rng() % 12;
bool weighted = trial % 2;
std::vector<std::vector<std::pair<int, long long>>> g(n);
tree_diameter<long long> d(n);
for (int v = 1; v < n; v++) {
int p = rng() % v;
long long w = weighted ? rng() % 5 : 1;
g[v].emplace_back(p, w);
g[p].emplace_back(v, w);
d.add_edge(p, v, w);
}
d.build();
std::vector<std::vector<long long>> dist(n, std::vector<long long>(n, -1));
for (int s = 0; s < n; s++) {
std::vector<int> st = {s};
dist[s][s] = 0;
while (!st.empty()) {
int x = st.back();
st.pop_back();
for (auto [y, w] : g[x]) {
if (dist[s][y] != -1) continue;
dist[s][y] = dist[s][x] + w;
st.push_back(y);
}
}
}
long long diam = 0;
for (int s = 0; s < n; s++) diam = std::max(diam, *std::max_element(dist[s].begin(), dist[s].end()));
assert(d.length() == diam);
auto [u, v] = d.ends();
assert(dist[u][v] == diam);
const std::vector<int>& path = d.path();
assert(path.front() == u && path.back() == v);
long long len = 0;
for (int i = 0; i + 1 < int(path.size()); i++) {
bool found = false;
for (auto [y, w] : g[path[i]]) {
if (y == path[i + 1]) found = true, len += w;
}
assert(found);
}
assert(len == diam);
auto [a, b] = d.center();
std::vector<long long> ecc(n);
for (int s = 0; s < n; s++) ecc[s] = *std::max_element(dist[s].begin(), dist[s].end());
if (a == b) {
assert(0 <= a && a < n);
assert(2 * ecc[a] == diam);
} else {
long long w = -1;
for (auto [y, ww] : g[a]) {
if (y == b) w = ww;
}
assert(w > 0);
double t = diam / 2.0 - dist[u][a];
assert(0 < t && t < w);
double e = 0;
for (int x = 0; x < n; x++) e = std::max(e, std::min(dist[a][x] + t, dist[b][x] + w - t));
assert(e == diam / 2.0);
}
}
std::cout << "Hello World" << std::endl;
return 0;
}#line 1 "test/unit/tree_diameter.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <vector>
#line 4 "graph/tree_diameter.hpp"
#include <utility>
#line 6 "graph/tree_diameter.hpp"
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 9 "test/unit/tree_diameter.test.cpp"
int main() {
std::mt19937 rng(20261028);
for (int trial = 0; trial < 300; trial++) {
int n = 1 + rng() % 12;
bool weighted = trial % 2;
std::vector<std::vector<std::pair<int, long long>>> g(n);
tree_diameter<long long> d(n);
for (int v = 1; v < n; v++) {
int p = rng() % v;
long long w = weighted ? rng() % 5 : 1;
g[v].emplace_back(p, w);
g[p].emplace_back(v, w);
d.add_edge(p, v, w);
}
d.build();
std::vector<std::vector<long long>> dist(n, std::vector<long long>(n, -1));
for (int s = 0; s < n; s++) {
std::vector<int> st = {s};
dist[s][s] = 0;
while (!st.empty()) {
int x = st.back();
st.pop_back();
for (auto [y, w] : g[x]) {
if (dist[s][y] != -1) continue;
dist[s][y] = dist[s][x] + w;
st.push_back(y);
}
}
}
long long diam = 0;
for (int s = 0; s < n; s++) diam = std::max(diam, *std::max_element(dist[s].begin(), dist[s].end()));
assert(d.length() == diam);
auto [u, v] = d.ends();
assert(dist[u][v] == diam);
const std::vector<int>& path = d.path();
assert(path.front() == u && path.back() == v);
long long len = 0;
for (int i = 0; i + 1 < int(path.size()); i++) {
bool found = false;
for (auto [y, w] : g[path[i]]) {
if (y == path[i + 1]) found = true, len += w;
}
assert(found);
}
assert(len == diam);
auto [a, b] = d.center();
std::vector<long long> ecc(n);
for (int s = 0; s < n; s++) ecc[s] = *std::max_element(dist[s].begin(), dist[s].end());
if (a == b) {
assert(0 <= a && a < n);
assert(2 * ecc[a] == diam);
} else {
long long w = -1;
for (auto [y, ww] : g[a]) {
if (y == b) w = ww;
}
assert(w > 0);
double t = diam / 2.0 - dist[u][a];
assert(0 < t && t < w);
double e = 0;
for (int x = 0; x < n; x++) e = std::max(e, std::min(dist[a][x] + t, dist[b][x] + w - t));
assert(e == diam / 2.0);
}
}
std::cout << "Hello World" << std::endl;
return 0;
}