結果

問題 No.3113 The farthest point
ユーザー aoblue2547
提出日時 2025-04-19 10:35:40
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,138 bytes
コンパイル時間 6,719 ms
コンパイル使用メモリ 333,364 KB
実行使用メモリ 29,804 KB
最終ジャッジ日時 2025-04-19 10:35:52
合計ジャッジ時間 12,096 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other WA * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
template<class T> bool chmin(T& a, T b) { return a > b ? a = b, true : false; }
template<class T> bool chmax(T& a, T b) { return a < b ? a = b, true : false; }
template<typename T>
concept Iterable = requires(T t) { std::begin(t); std::end(t); };
template<typename T>
	requires Iterable<T> && (!is_same_v<T, string>)
ostream& operator<<(ostream& os, const T& container) { for (auto& element : container) os << element << ' '; return os; }
template<typename R>
	requires ranges::range<R> && (!is_same_v<decay_t<R>, string>) && (!is_same_v<decay_t<R>, const char*>)
ostream& operator<<(ostream& os, R&& range) { for (auto& element : range)os << element << ' '; return os; }
template<typename T>
	requires Iterable<T> && (!is_same_v<T, string>)
istream& operator>>(std::istream& is, T& container) { for (auto& e : container)is >> e; return is; }
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
template<class T = ll> struct Edge {
	int to;
	T weight;
	bool operator==(Edge e) { return this->to == e.to and this->weight == e.weight; }
	bool operator<(Edge e) { return this->to == e.to ? this->weight < e.weight : this->to < e.to; }
};
#ifdef _DEBUG
#define SHOW(n) {const auto& _ret = n; cerr << #n << ": " << _ret << endl;}
#define MSG(x) cerr << x << endl;
#else
#define SHOW(n)
#define MSG(x)
#endif

//AtCoder Library
#include <atcoder/all>
using namespace atcoder;
//using mint = modint998244353;
using mint = modint1000000007;
//using mint1 = dynamic_modint<0>;
//using mint = modint;
//mint::set_mod();
istream& operator>>(istream& is, mint& x) { ll r; is >> r; x = r; return is; }
ostream& operator<<(ostream& os, mint& x) { os << x.val(); return os; }

//boost
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
//using l3 = int128_t;



int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;
	vector<vector<Edge<ll>>> g(n);
	for (int i = 0; i < n - 1; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		--a, --b;
		g[a].push_back({ b, c });
		g[b].push_back({ a, c });
	}


	ll INF = 1e18;
	ll res = 0;

	vector<vector<ll>> dp(n);


	auto dfs = [&](auto&& f, int v, int prev)->void {
		int deg = g[v].size();
		dp[v].resize(deg, -INF);

		bool update = false;
		for (int i = 0; i < deg; ++i) {
			auto [s, w] = g[v][i];
			if (s == prev)continue;
			update = true;
			f(f, s, v);
			chmax(dp[v][i], dp[s][0] + w);
		}

		ranges::sort(dp[v], ranges::greater());

		if (not update)dp[v][0] = 0;
		};

	dfs(dfs, 0, -1);

	auto dfs2 = [&](auto&& f, int v, int prev, ll pval)->void {
		int deg = g[v].size();
		for (int i = 0; i < deg; ++i) {
			auto [s, w] = g[v][i];
			if (s == prev)dp[v][i] = pval;
		}

		ranges::sort(dp[v], ranges::greater());

		for (int i = 0; i < deg; ++i) {
			auto [s, w] = g[v][i];
			if (s == prev)continue;
			ll p = dp[v][0];
			f(f, s, v, p);
		}
		};

	dfs2(dfs2, 0, -1, 0);

	for (int i = 0; i < n; ++i) {
		ll r = 0;
		int deg = g[i].size();
		for (int j = 0; j < min(2, deg); ++j) {
			r += dp[i][j];
		}
		chmax(res, r);
	}

	cout << res << endl;



	return 0;
}
0