test/tree/rerooting_dp/aoj_grl_5_b.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_B

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_B

#include "src/tree/rerooting_dp.hpp"

#include <algorithm>
#include <iostream>

using namespace std;

int main() {
	int n;
	cin >> n;
	auto f = [](int a, int b) { return max(a, b); };
	auto g = [](int a, int b) { return a + b; };
	RerootingDP<int, int, decltype(f), decltype(g)> dp(n, f, g, 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();
	for (auto e : dp.reroot()) cout << e << endl;

	return 0;
}

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

#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_b.test.cpp"

#include <algorithm>
#include <iostream>

using namespace std;

int main() {
	int n;
	cin >> n;
	auto f = [](int a, int b) { return max(a, b); };
	auto g = [](int a, int b) { return a + b; };
	RerootingDP<int, int, decltype(f), decltype(g)> dp(n, f, g, 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();
	for (auto e : dp.reroot()) cout << e << endl;

	return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	13 ms	7 MB
g++	00_sample_01.in	AC	12 ms	7 MB
g++	01_minimum_00.in	AC	13 ms	7 MB
g++	01_minimum_01.in	AC	12 ms	7 MB
g++	01_minimum_02.in	AC	12 ms	7 MB
g++	01_minimum_03.in	AC	12 ms	7 MB
g++	02_small_00.in	AC	12 ms	7 MB
g++	02_small_01.in	AC	13 ms	7 MB
g++	02_small_02.in	AC	13 ms	7 MB
g++	50-random00.in	AC	19 ms	8 MB
g++	50-random01.in	AC	32 ms	9 MB
g++	50-random02.in	AC	27 ms	8 MB
g++	50-random03.in	AC	29 ms	9 MB
g++	50-random04.in	AC	36 ms	9 MB
g++	50-random05.in	AC	39 ms	9 MB
g++	50-random06.in	AC	40 ms	9 MB
g++	50-random07.in	AC	40 ms	9 MB
g++	50-random08.in	AC	40 ms	9 MB
g++	50-random09.in	AC	39 ms	9 MB
g++	50-random10.in	AC	39 ms	9 MB
g++	corner01-00.in	AC	48 ms	20 MB
g++	corner01-01.in	AC	50 ms	20 MB
g++	corner01-02.in	AC	52 ms	20 MB
g++	corner01-03.in	AC	50 ms	20 MB
g++	corner01-04.in	AC	52 ms	20 MB
g++	corner01-05.in	AC	55 ms	20 MB
g++	corner02-00.in	AC	40 ms	9 MB
g++	corner02-01.in	AC	39 ms	9 MB
g++	corner02-02.in	AC	38 ms	9 MB
g++	corner02-03.in	AC	37 ms	9 MB
g++	corner02-04.in	AC	37 ms	9 MB
g++	corner02-05.in	AC	37 ms	9 MB
clang++	00_sample_00.in	AC	12 ms	7 MB
clang++	00_sample_01.in	AC	12 ms	15 MB
clang++	01_minimum_00.in	AC	11 ms	9 MB
clang++	01_minimum_01.in	AC	11 ms	7 MB
clang++	01_minimum_02.in	AC	11 ms	9 MB
clang++	01_minimum_03.in	AC	11 ms	11 MB
clang++	02_small_00.in	AC	11 ms	11 MB
clang++	02_small_01.in	AC	11 ms	9 MB
clang++	02_small_02.in	AC	11 ms	9 MB
clang++	50-random00.in	AC	18 ms	14 MB
clang++	50-random01.in	AC	32 ms	15 MB
clang++	50-random02.in	AC	26 ms	15 MB
clang++	50-random03.in	AC	29 ms	9 MB
clang++	50-random04.in	AC	37 ms	16 MB
clang++	50-random05.in	AC	40 ms	16 MB
clang++	50-random06.in	AC	39 ms	12 MB
clang++	50-random07.in	AC	39 ms	14 MB
clang++	50-random08.in	AC	38 ms	14 MB
clang++	50-random09.in	AC	42 ms	12 MB
clang++	50-random10.in	AC	40 ms	12 MB
clang++	corner01-00.in	AC	48 ms	20 MB
clang++	corner01-01.in	AC	44 ms	22 MB
clang++	corner01-02.in	AC	47 ms	16 MB
clang++	corner01-03.in	AC	47 ms	16 MB
clang++	corner01-04.in	AC	44 ms	16 MB
clang++	corner01-05.in	AC	47 ms	18 MB
clang++	corner02-00.in	AC	35 ms	12 MB
clang++	corner02-01.in	AC	38 ms	10 MB
clang++	corner02-02.in	AC	37 ms	10 MB
clang++	corner02-03.in	AC	37 ms	12 MB
clang++	corner02-04.in	AC	38 ms	10 MB
clang++	corner02-05.in	AC	36 ms	14 MB

Back to top page