Submission #535036

---

Source Code Expand

#include <utility>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <iterator>
#include <iostream>
namespace lc {
struct Edge {
	int to;
	explicit Edge(int to) : to(to) { }
};
}
namespace lc {
template <typename EdgeType>
class AdjacencyList {
public:
	typedef std::vector<EdgeType> ListType;
private:
	std::vector<ListType> m_lists;
public:
	explicit AdjacencyList(int n = 0)
		: m_lists(n)
	{ }
	int size() const { return m_lists.size(); }
	template <typename... Args>
	void add_edge(int u, Args&&... args){
		m_lists[u].emplace_back(args...);
	}
	const ListType &operator[](int u) const { return m_lists[u]; }
};
}
namespace lc {
class HeavyLightDecomposer {
public:
	struct Connection {
		int local_index;
		int child_path;
		explicit Connection(int li = -1, int cp = -1) :
			local_index(li), child_path(cp)
		{ }
	};
	struct Segment {
		int path;
		int first;
		int last;
		explicit Segment(int path = -1, int first = -1, int last = -1) :
			path(path), first(first), last(last)
		{ }
	};
private:
	typedef std::pair<int, int> pii;
	struct Path {
		int parent_vertex;
		std::vector<Connection> children;
		std::vector<int> vertices;
		int depth;
	};
	std::vector<Path> m_paths;
	std::vector<int> m_path_ids;
	std::vector<int> m_local_indices;
	template <typename EdgeType>
	std::vector<int> compute_subtree_size(
		const AdjacencyList<EdgeType> &conn, int root) const
	{
		const int n = conn.size();
		std::vector<int> subtree_size(n);
		std::vector<bool> passed(n), gathered(n);
		std::stack<pii> count_stack;
		count_stack.push(pii(root, 0));
		while(!count_stack.empty()){
			const pii p = count_stack.top();
			count_stack.pop();
			const int u = p.first, i = p.second;
			if(i == 0){
				passed[u] = true;
				count_stack.push(pii(u, 1));
				for(size_t j = 0; j < conn[u].size(); ++j){
					const int v = conn[u][j].to;
					if(passed[v]){ continue; }
					count_stack.push(pii(v, 0));
				}
			}else{
				int sum = 1;
				gathered[u] = true;
				for(size_t j = 0; j < conn[u].size(); ++j){
					const int v = conn[u][j].to;
					if(!gathered[v]){ continue; }
					sum += subtree_size[v];
				}
				subtree_size[u] = sum;
			}
		}
		return subtree_size;
	}
public:
	template <typename EdgeType>
	explicit HeavyLightDecomposer(
		const AdjacencyList<EdgeType> &conn, int root = 0)
		: m_paths(0)
		, m_path_ids(conn.size(), -1)
		, m_local_indices(conn.size(), -1)
	{
		const std::vector<int> subtree_size = compute_subtree_size(conn, root);
		std::stack<pii> decompose_stack;
		decompose_stack.push(pii(root, -1));
		while(!decompose_stack.empty()){
			const pii p = decompose_stack.top();
			decompose_stack.pop();
			const int parent_vertex = p.second;
			const int pid = m_paths.size();
			m_paths.push_back(Path());
			Path &path = m_paths.back();
			path.parent_vertex = parent_vertex;
			if(parent_vertex >= 0){
				const int parent_pid = m_path_ids[parent_vertex];
				const int parent_index = m_local_indices[parent_vertex];
				m_paths[parent_pid].children.push_back(
					Connection(parent_index, pid));
				path.depth = m_paths[parent_pid].depth + 1;
			}else{
				path.depth = 0;
			}
			int cur = p.first;
			while(cur >= 0){
				const int st_size = subtree_size[cur], threshold = st_size / 2;
				m_path_ids[cur] = pid;
				m_local_indices[cur] = path.vertices.size();
				path.vertices.push_back(cur);
				int heavy_edge = -1;
				for(size_t i = 0; i < conn[cur].size(); ++i){
					const int v = conn[cur][i].to;
					if(subtree_size[v] > subtree_size[cur]){ continue; }
					if(heavy_edge < 0 && subtree_size[v] >= threshold){
						heavy_edge = v;
					}else{
						decompose_stack.push(pii(v, cur));
					}
				}
				cur = heavy_edge;
			}
		}
	}
	int path_count() const { return m_paths.size(); }
	int path_length(int p) const { return m_paths[p].vertices.size(); }
	int path_depth(int p) const { return m_paths[p].depth; }
	int parent_path_id(int p) const {
		if(m_paths[p].parent_vertex < 0){ return -1; }
		return m_path_ids[m_paths[p].parent_vertex];
	}
	int parent_local_index(int p) const {
		if(m_paths[p].parent_vertex < 0){ return -1; }
		return m_local_indices[m_paths[p].parent_vertex];
	}
	int path_id(int v) const { return m_path_ids[v]; }
	int local_index(int v) const { return m_local_indices[v]; }
	int vertex_id(int p, int i) const { return m_paths[p].vertices[i]; }
	std::vector<Segment> shortest_path(int u, int v) const {
		std::vector<Segment> usegs, vsegs, result;
		int up = path_id(u), ul = local_index(u);
		int vp = path_id(v), vl = local_index(v);
		while(up != vp){
			const bool update_u = path_depth(up) >= path_depth(vp);
			const bool update_v = path_depth(up) <= path_depth(vp);
			if(update_u){
				usegs.push_back(Segment(up, 0, ul + 1));
				ul = parent_local_index(up);
				up = parent_path_id(up);
			}
			if(update_v){
				vsegs.push_back(Segment(vp, 0, vl + 1));
				vl = parent_local_index(vp);
				vp = parent_path_id(vp);
			}
		}
		for(int i = 0; i < static_cast<int>(usegs.size()); ++i){
			const Segment &s = usegs[i];
			result.push_back(Segment(s.path, s.last - 1, s.first - 1));
		}
		result.push_back(Segment(up, ul, vl + (ul > vl ? -1 : 1)));
		for(int i = static_cast<int>(vsegs.size()) - 1; i >= 0; --i){
			result.push_back(vsegs[i]);
		}
		return result;
	}
};
}
using namespace std;
typedef lc::Edge Edge;
static const int INF = 1000000010;
class SegmentTree {
public:
	typedef int value_type;
private:
	int m_size;
	std::vector<value_type> m_data;
	void initialize(){
		for(int i = m_size - 2; i >= 0; --i){
			m_data[i] = min(m_data[i * 2 + 1], m_data[i * 2 + 2]);
		}
	}
	value_type query(int a, int b, int k, int l, int r) const {
		if(r <= a || b <= l){ return INF; }
		if(a <= l && r <= b){ return m_data[k]; }
		const value_type vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
		const value_type vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
		return min(vl, vr);
	}
	int query_left(int x, int a, int b, int k, int l, int r) const {
		if(r <= a || b <= l){ return -1; }
		if(k >= m_size - 1){ return k - (m_size - 1); }
		const value_type vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
		if(vl <= x){
			return query_left(x, a, b, k * 2 + 1, l, (l + r) / 2);
		}else{
			return query_left(x, a, b, k * 2 + 2, (l + r) / 2, r);
		}
	}
	int query_right(int x, int a, int b, int k, int l, int r) const {
		if(r <= a || b <= l){ return -1; }
		if(k >= m_size - 1){ return k - (m_size - 1); }
		const value_type vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
		if(vr <= x){
			return query_right(x, a, b, k * 2 + 2, (l + r) / 2, r);
		}else{
			return query_right(x, a, b, k * 2 + 1, l, (l + r) / 2);
		}
	}
public:
	template <typename Iterator>
	SegmentTree(Iterator first, Iterator last) :
		m_size(1), m_data()
	{
		const int n = std::distance(first, last);
		while(m_size < n){ m_size *= 2; }
		m_data.resize(m_size * 2 - 1, INF);
		std::copy(first, last, m_data.begin() + m_size - 1);
		initialize();
	}
	value_type query(int a, int b) const {
		return query(a, b, 0, 0, m_size);
	}
	int query_left(int x, int a, int b) const {
		return query_left(x, a, b, 0, 0, m_size);
	}
	int query_right(int x, int a, int b) const {
		return query_right(x, a, b, 0, 0, m_size);
	}
	value_type operator[](int i) const {
		return m_data[m_size - 1 + i];
	}
};
int main(){
	ios_base::sync_with_stdio(false);
	int n, q;
	cin >> n >> q;
	vector<int> a(n);
	for(int i = 0; i < n; ++i){ cin >> a[i]; }
	lc::AdjacencyList<Edge> graph(n);
	for(int i = 0; i + 1 < n; ++i){
		int b, c;
		cin >> b >> c;
		--b; --c;
		graph.add_edge(b, c);
		graph.add_edge(c, b);
	}
	lc::HeavyLightDecomposer decomp(graph);
	vector<SegmentTree> ntables;
	for(int i = 0; i < decomp.path_count(); ++i){
		const int len = decomp.path_length(i);
		vector<int> raw_path(len);
		for(int j = 0; j < len; ++j){
			raw_path[j] = a[decomp.vertex_id(i, j)];
		}
		ntables.emplace_back(raw_path.begin(), raw_path.end());
	}
	while(q--){
		int x, v, w;
		cin >> x >> v >> w;
		--v; --w;
		const auto segs = decomp.shortest_path(v, w);
		for(const auto &seg : segs){
			const auto &ntable = ntables[seg.path];
			if(seg.first < seg.last){
				int l = seg.first, r = seg.last;
				while(ntable.query(l, r) <= x){
					const int p = ntable.query_left(x, l, r);
					x %= ntable[p];
				}
			}else{
				int l = seg.last + 1, r = seg.first + 1;
				while(ntable.query(l, r) <= x){
					const int p = ntable.query_right(x, l, r);
					x %= ntable[p];
				}
			}
		}
		cout << x << endl;
	}
	return 0;
}

Submission Info

Judge Result