木の直径を求める (daylight/graph/diameter.hpp)

View this file on GitHub
Last update: 2024-12-26 20:32:55+09:00
Include: #include "daylight/graph/diameter.hpp"

Depends on

Required by

daylight/graph/all.hpp

Verified with

test/yosupo/tree/tree_diameter.test.cpp

Code

#include "daylight/base.hpp"
#include "daylight/graph/base.hpp"

/// @brief 木の直径を求める

namespace inner_diameter {
pair<ll, int> dfs(int cur, int pre, Graph<> &G) {
	pair<ll, int> p { 0, cur };
	for(Edge e: G[cur]) {
		if(e.to == pre) continue;
		auto [dis, v] = dfs(e.to, cur, G);
		chmax(p, { dis + e.cost, v });
	}
	return p;
}
}

pair<ll, pair<int, int>> get_diameter(Graph<> &G) {
	auto [dis, v] = inner_diameter::dfs(0, -1, G);
	auto [dis2, v2] = inner_diameter::dfs(v, -1, G);
	return { dis2, { v, v2 } };
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj_resolve/resolver.py", line 181, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 252, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 482, in update
    self.update(
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 477, in update
    raise BundleErrorAt(
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: daylight/base.hpp: line 103: unable to process #include in #if / #ifdef / #ifndef other than include guards