Submission #2504609

---

Source Code Expand

#include <utility>
#include <cstddef>
#include <numeric>
#include <stack>
#include <iostream>
#include <functional>
#include <vector>
#include <string>
#include <array>
#include <algorithm>
namespace loquat {
using vertex_t = size_t;
}
namespace loquat {
namespace edge_param {
struct to_ {
	vertex_t to;
	explicit to_(vertex_t t = 0)
		: to(t)
	{ }
};
}
namespace detail {
template <typename T, typename... Params>
struct edge_param_wrapper : public T, edge_param_wrapper<Params...> {
};
template <typename T>
struct edge_param_wrapper<T> : public T {
	template <typename U>
	explicit edge_param_wrapper(U&& x)
		: T(std::forward<U>(x))
	{ }
};
}
template <typename... Params>
struct edge : public detail::edge_param_wrapper<edge_param::to_, Params...> {
	template <typename... Args>
	explicit edge(Args&&... args)
		: detail::edge_param_wrapper<edge_param::to_, Params...>(
			std::forward<Args>(args)...)
	{ }
};
}
namespace loquat {
template <typename EdgeType>
class adjacency_list {
public:
	using edge_type = EdgeType;
	using edge_list = std::vector<edge_type>;
private:
	std::vector<std::vector<EdgeType>> m_edges;
public:
	explicit adjacency_list(size_t n)
		: m_edges(n)
	{ }
	size_t size() const {
		return m_edges.size();
	}
	const edge_list& operator[](vertex_t u) const {
		return m_edges[u];
	}
	edge_list& operator[](vertex_t u){
		return m_edges[u];
	}
	template <typename... Args>
	void add_edge(vertex_t from, Args&&... args){
		m_edges[from].emplace_back(std::forward<Args>(args)...);
	}
};
}
namespace loquat {
template <typename EdgeType, typename Behavior, typename... Args>
std::vector<typename Behavior::state_type>
undirected_tree_dynamic_programming(
	const adjacency_list<EdgeType>& graph,
	Behavior behavior,
	Args&&... args)
{
	using state_type = typename Behavior::state_type;
	using frame_type = std::pair<vertex_t, size_t>;
	const size_t n = graph.size();
	std::vector<state_type> temporary(n), result(n);
	for(vertex_t v = 0; v < n; ++v){
		temporary[v] = behavior.initial(v, args...);
	}
	std::stack<frame_type> frames;
	frames.emplace(0, 0);
	while(!frames.empty()){
		const auto frame = frames.top();
		frames.pop();
		const auto u = frame.first;
		const auto i = frame.second;
		const vertex_t p = (frames.empty() ? u : frames.top().first);
		if(i == graph[u].size()){
			for(const auto& e : graph[u]){
				if(e.to == p){ continue; }
				const auto& x = temporary[e.to];
				const auto& y = temporary[u];
				temporary[u] = behavior.merge(y, x, u, e, args...);
			}
		}else{
			const auto& e = graph[u][i];
			frames.emplace(u, i + 1);
			if(e.to != p){ frames.emplace(e.to, 0); }
		}
	}
	frames.emplace(0, 0);
	result[0] = temporary[0];
	while(!frames.empty()){
		const auto frame = frames.top();
		frames.pop();
		const auto u = frame.first;
		const auto i = frame.second;
		const vertex_t p = (frames.empty() ? u : frames.top().first);
		if(i == 0){
			for(const auto& e : graph[u]){
				if(e.to == p){
					const auto& x = temporary[e.to];
					const auto& y = temporary[u];
					result[u] = behavior.merge(y, x, u, e, args...);
					break;
				}
			}
		}
		if(i != graph[u].size()){
			const auto& e = graph[u][i];
			frames.emplace(u, i + 1);
			if(e.to != p){
				const auto& x = temporary[e.to];
				const auto& y = result[u];
				temporary[u] = behavior.purge(y, x, u, e, args...);
				frames.emplace(e.to, 0);
			}
		}
	}
	return result;
}
}
namespace loquat {
template <typename T, size_t K, typename Comparator = std::less<T>>
class top_k {
public:
	using value_type = T;
private:
	Comparator m_comparator;
	size_t m_size;
	std::array<T, K> m_data;
public:
	top_k()
		: m_comparator()
		, m_size(0)
		, m_data()
	{ }
	bool empty() const {
		return m_size == 0;
	}
	size_t size() const {
		return m_size;
	}
	const value_type& operator[](size_t i) const {
		return m_data[i];
	}
	void push(const value_type& x){
		if(m_size == K && !m_comparator(x, m_data[m_size - 1])){ return; }
		if(m_size == K){
			m_data[m_size - 1] = x;
		}else{
			m_data[m_size++] = x;
		}
		for(size_t i = m_size - 1; i > 0; --i){
			if(m_comparator(m_data[i], m_data[i - 1])){
				std::swap(m_data[i], m_data[i - 1]);
			}
		}
	}
};
}
using namespace std;
using edge = loquat::edge<>;
struct behavior {
	using state_type = loquat::top_k<int, 2, std::greater<int>>;
	using edge_type = edge;
	state_type initial(loquat::vertex_t v, const vector<int>& c) const {
		state_type s;
		s.push(c[v]);
		return s;
	}
	state_type merge(
		state_type y,
		const state_type& x,
		loquat::vertex_t u,
		const edge_type& e,
		const vector<int>& c) const
	{
		if(!x.empty()){ y.push(x[0] + c[u]); }
		return y;
	}
	state_type purge(
		const state_type& y,
		const state_type& x,
		loquat::vertex_t u,
		const edge_type& e,
		const vector<int>& c) const
	{
		if(!x.empty() && !y.empty() && y[0] == x[0] + c[u]){
			state_type z;
			if(y.size() > 1){ z.push(y[1]); }
			return z;
		}else{
			return y;
		}
	}
};
int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	loquat::adjacency_list<edge> g(n);
	for(int i = 1; i < n; ++i){
		int a, b;
		cin >> a >> b;
		--a; --b;
		g.add_edge(a, b);
		g.add_edge(b, a);
	}
	string s;
	cin >> s;
	vector<int> deg(n);
	for(int i = 0; i < n; ++i){ deg[i] = g[i].size(); }
	for(int i = 0; i < n; ++i){
		int u = i;
		while(deg[u] == 1 && s[u] == 'B'){
			int v = -1;
			for(const auto& e : g[u]){
				v = e.to;
				if(deg[v] > 0){ break; }
			}
			--deg[u];
			--deg[v];
			u = v;
		}
	}
	vector<int> c(n);
	for(int i = 0; i < n; ++i){
		const int x = (s[i] == 'W' ? 0 : 1);
		c[i] = 1 - (x ^ (deg[i] & 1));
	}
	const auto dp = loquat::undirected_tree_dynamic_programming(g, behavior(), c);
	int shortcut = 0;
	for(const auto& p : dp){
		if(!p.empty()){ shortcut = max(shortcut, p[0]); }
	}
	const int d = shortcut * 2 - accumulate(c.begin(), c.end(), 0);
	int k = 0;
	for(int i = 0; i < n; ++i){
		if(deg[i] > 0){ ++k; }
	}
	if(k == 0){
		cout << (find(s.begin(), s.end(), 'W') != s.end() ? 1 : 0) << endl;
	}else{
		const int answer = (k - 1) * 2 - d;
		cout << answer << endl;
	}
	return 0;
}

Submission Info

Judge Result