test/tree/rerooting_dp/aoj_grl_5_a.test.cpp

• View this file on GitHub
• Last update: 2024-04-29 16:58:35+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/5/GRL_5_A

Depends on

• Rerooting DP (src/tree/rerooting_dp.hpp)

Code

// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/5/GRL_5_A

#include "src/tree/rerooting_dp.hpp"

#include <algorithm>
#include <iostream>
#include <utility>

using namespace std;

int main() {
	int n;
	cin >> n;
	auto f = [](pair<int, int> a, pair<int, int> b) {
		int tmp = max(a.first, b.first);
		return pair(tmp, max({a.first + b.first - tmp, a.second, b.second}));
	};
	auto g = [](pair<int, int> a, int b) { return pair(a.first + b, 0); };
	RerootingDP<pair<int, int>, int, decltype(f), decltype(g)> dp(n, f, g, pair(0, 0));
	for (int i = 0; i < n - 1; ++i) {
		int s, t, w;
		cin >> s >> t >> w;
		dp.add_edge(s, t, w);
	}

	dp.build();
	int ans = 0;
	for (auto e : dp.reroot()) ans = max(ans, e.first + e.second);
	cout << ans << endl;

	return 0;
}

#line 1 "test/tree/rerooting_dp/aoj_grl_5_a.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/5/GRL_5_A

#line 1 "src/tree/rerooting_dp.hpp"



#include <utility>
#include <vector>

template<class T, class E, class F, class G>
class RerootingDP {
private:
	std::vector<std::vector<std::pair<int, E>>> graph;
	std::vector<T> dp1, dp2;
	F f; // function<T(T, T)>
	G g; // function<T(T, E)>
	T ti;

	void dfs(int v, int p) {
		for (auto const &[nv, e] : graph[v]) {
			if (nv == p) continue;
			dfs(nv, v);
			dp1[v] = f(dp1[v], g(dp1[nv], e));
		}
	}

	void dfs2(int v, int p, T ndp) {
		int size = graph[v].size();
		std::vector<T> lcum(size + 1, ti), rcum(size + 1, ti);

		for (int i = 0; i < size; ++i) {
			auto const &[nv, e] = graph[v][i];
			if (nv == p) lcum[i + 1] = f(lcum[i], g(ndp, e));
			else lcum[i + 1] = f(lcum[i], g(dp1[nv], e));
		}
		for (int i = size - 1; i >= 0; --i) {
			auto const &[nv, e] = graph[v][i];
			if (nv == p) rcum[i] = f(g(ndp, e), rcum[i + 1]);
			else rcum[i] = f(g(dp1[nv], e), rcum[i + 1]);
		}

		dp2[v] = lcum.back();
		for (int i = 0; i < size; ++i) {
			auto const &[nv, e] = graph[v][i];
			if (nv == p) continue;
			dfs2(nv, v, f(lcum[i], rcum[i + 1]));
		}
	}

public:
	RerootingDP(int n, F f, G g, T ti) :
		graph(n), dp1(n), dp2(n), f(f), g(g), ti(std::move(ti)) {}

	void add_edge(int u, int v, E const &e) {
		graph[u].emplace_back(v, e);
		graph[v].emplace_back(u, e);
	}

	std::vector<T> build(int v = 0, int p = -1) {
		dfs(v, p);
		return dp1;
	}

	std::vector<T> reroot(int v = 0, int p = -1) { return reroot(v, p, ti); }

	std::vector<T> reroot(int v, int p, T ndp) {
		dfs2(v, p, ndp);
		return dp2;
	}
};


#line 4 "test/tree/rerooting_dp/aoj_grl_5_a.test.cpp"

#include <algorithm>
#include <iostream>
#line 8 "test/tree/rerooting_dp/aoj_grl_5_a.test.cpp"

using namespace std;

int main() {
	int n;
	cin >> n;
	auto f = [](pair<int, int> a, pair<int, int> b) {
		int tmp = max(a.first, b.first);
		return pair(tmp, max({a.first + b.first - tmp, a.second, b.second}));
	};
	auto g = [](pair<int, int> a, int b) { return pair(a.first + b, 0); };
	RerootingDP<pair<int, int>, int, decltype(f), decltype(g)> dp(n, f, g, pair(0, 0));
	for (int i = 0; i < n - 1; ++i) {
		int s, t, w;
		cin >> s >> t >> w;
		dp.add_edge(s, t, w);
	}

	dp.build();
	int ans = 0;
	for (auto e : dp.reroot()) ans = max(ans, e.first + e.second);
	cout << ans << endl;

	return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	87 ms	7 MB
g++	00_sample_01.in	AC	13 ms	7 MB
g++	01_small_00.in	AC	13 ms	7 MB
g++	01_small_01.in	AC	12 ms	7 MB
g++	01_small_02.in	AC	12 ms	7 MB
g++	01_small_03.in	AC	13 ms	7 MB
g++	02_medium_00.in	AC	13 ms	7 MB
g++	02_medium_01.in	AC	13 ms	7 MB
g++	02_medium_02.in	AC	13 ms	7 MB
g++	02_medium_03.in	AC	13 ms	7 MB
g++	03_corner_00.in	AC	12 ms	7 MB
g++	03_corner_01.in	AC	12 ms	7 MB
g++	04_binary_00.in	AC	13 ms	7 MB
g++	04_binary_01.in	AC	13 ms	7 MB
g++	04_binary_02.in	AC	13 ms	7 MB
g++	04_binary_03.in	AC	14 ms	7 MB
g++	05_linear_00.in	AC	14 ms	8 MB
g++	05_linear_01.in	AC	17 ms	10 MB
g++	05_linear_02.in	AC	21 ms	12 MB
g++	05_linear_03.in	AC	29 ms	18 MB
g++	06_rand_00.in	AC	13 ms	7 MB
g++	06_rand_01.in	AC	14 ms	7 MB
g++	06_rand_02.in	AC	23 ms	8 MB
g++	06_rand_03.in	AC	32 ms	10 MB
g++	07_large_00.in	AC	52 ms	12 MB
g++	07_large_01.in	AC	74 ms	15 MB
g++	07_large_02.in	AC	78 ms	15 MB
g++	07_large_03.in	AC	119 ms	73 MB
g++	08_maximum_00.in	AC	184 ms	30 MB
g++	08_maximum_01.in	AC	199 ms	31 MB
g++	08_maximum_02.in	AC	218 ms	34 MB
g++	08_maximum_03.in	AC	439 ms	272 MB
clang++	00_sample_00.in	AC	11 ms	9 MB
clang++	00_sample_01.in	AC	12 ms	15 MB
clang++	01_small_00.in	AC	12 ms	11 MB
clang++	01_small_01.in	AC	11 ms	9 MB
clang++	01_small_02.in	AC	11 ms	9 MB
clang++	01_small_03.in	AC	12 ms	9 MB
clang++	02_medium_00.in	AC	11 ms	9 MB
clang++	02_medium_01.in	AC	12 ms	13 MB
clang++	02_medium_02.in	AC	12 ms	15 MB
clang++	02_medium_03.in	AC	12 ms	13 MB
clang++	03_corner_00.in	AC	12 ms	11 MB
clang++	03_corner_01.in	AC	11 ms	11 MB
clang++	04_binary_00.in	AC	12 ms	11 MB
clang++	04_binary_01.in	AC	12 ms	11 MB
clang++	04_binary_02.in	AC	12 ms	9 MB
clang++	04_binary_03.in	AC	13 ms	8 MB
clang++	05_linear_00.in	AC	13 ms	12 MB
clang++	05_linear_01.in	AC	15 ms	16 MB
clang++	05_linear_02.in	AC	19 ms	15 MB
clang++	05_linear_03.in	AC	26 ms	21 MB
clang++	06_rand_00.in	AC	12 ms	13 MB
clang++	06_rand_01.in	AC	13 ms	12 MB
clang++	06_rand_02.in	AC	21 ms	13 MB
clang++	06_rand_03.in	AC	31 ms	16 MB
clang++	07_large_00.in	AC	51 ms	21 MB
clang++	07_large_01.in	AC	73 ms	23 MB
clang++	07_large_02.in	AC	74 ms	19 MB
clang++	07_large_03.in	AC	105 ms	63 MB
clang++	08_maximum_00.in	AC	187 ms	32 MB
clang++	08_maximum_01.in	AC	201 ms	35 MB
clang++	08_maximum_02.in	AC	221 ms	34 MB
clang++	08_maximum_03.in	AC	391 ms	201 MB

Back to top page