Milk Visits

Análisis oficial (offline)

Para resolver este problema online, necesitamos hallar de forma eficiente el ancestro más cercano de una granja $x$ con un cierto tipo de leche. Aquí hay varias formas de hacer esto.

Método 1

Ejecutamos el mismo DFS mencionado en el análisis. Para cada tipo de leche, almacenamos los índices del tour de Euler en los que cambia la respuesta. Luego podemos obtener la respuesta para un vértice usando una sola operación lower_bound sobre el vector del tipo de leche correspondiente.

Implementación

Complejidad temporal: $\mathcal{O}(\log N)$ por consulta.

C++


#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1000000007;
const int MX = 200005;
 
int T[MX];
 
template <int SZ> struct LCA {
	static const int BITS = 32 - __builtin_clz(SZ);
	int n, r = 1, cnt = 0, label[SZ];
	vector<int> adj[SZ], curr_node[SZ];
	vector<pair<int, int>> last_seen_node[SZ];
	int par[BITS][SZ], depth[SZ];
 
	void add_edge(int u, int v) {
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
 
	void dfs(int u, int prev) {
		label[u] = cnt++;
		curr_node[T[u]].push_back(u);
		last_seen_node[T[u]].push_back({label[u], u});
		par[0][u] = prev;
		depth[u] = depth[prev] + 1;
		for (int v : adj[u]) {
			if (v != prev) { dfs(v, u); }
		}
 
		curr_node[T[u]].pop_back();
		last_seen_node[T[u]].push_back(
		    {cnt, curr_node[T[u]].size() ? curr_node[T[u]].back() : 0});
	}
 
	void init(int _N) {
		n = _N;
		dfs(r, 0);
		for (int k = 1; k < BITS; k++) {
			for (int i = 1; i <= n; i++) { par[k][i] = par[k - 1][par[k - 1][i]]; }
		}
	}
 
	int get_par(int a, int b) {
		for (int k = BITS - 1; k >= 0; k--) {
			if (b & (1 << k)) { a = par[k][a]; }
		}
		return a;
	}
 
	int lca(int u, int v) {
		if (depth[u] < depth[v]) { swap(u, v); }
		u = get_par(u, depth[u] - depth[v]);
		for (int k = BITS - 1; k >= 0; k--) {
			if (par[k][u] != par[k][v]) {
				u = par[k][u];
				v = par[k][v];
			}
		}
		return u == v ? u : par[0][u];
	}
 
	int dist(int u, int v) { return depth[u] + depth[v] - 2 * depth[lca(u, v)]; }
 
	int last(int a, int c) {
		auto it = upper_bound(begin(last_seen_node[c]), end(last_seen_node[c]),
		                      make_pair(label[a], MOD));
		if (it == begin(last_seen_node[c])) { return 0; }
		return prev(it)->second;
	}
};
 
void set_up(std::string name) {
	freopen((name + ".in").c_str(), "r", stdin);
	freopen((name + ".out").c_str(), "w", stdout);
}
 
LCA<MX> L;
int n, m;
 
int main() {
	set_up("milkvisits");
	cin >> n >> m;
	for (int i = 1; i <= n; i++) { cin >> T[i]; }
 
	for (int i = 0; i < n - 1; i++) {
		int x, y;
		cin >> x >> y;
		L.add_edge(x, y);
	}
 
	L.init(n);
	for (int i = 0; i < m; i++) {
		int A, B, C;
		cin >> A >> B >> C;
		int z = L.lca(A, B);
		int a = L.last(A, C);
 
		if (a && L.depth[a] >= L.depth[z]) {
			cout << 1;
			continue;
		}
		a = L.last(B, C);
		if (a && L.depth[a] >= L.depth[z]) {
			cout << 1;
			continue;
		}
		cout << 0;
	}
}

Método 2

Generamos un arreglo persistente para cada vértice donde los índices del arreglo corresponden a los tipos de leche.

Complejidad temporal: $\mathcal{O}(\log N)$ por consulta. Al parecer esto se puede hacer en $\mathcal{O}(\log \log N)$ por consulta (paper ). ¿Es esta cota óptima para este problema?

Método 3

Usamos HLD. Podemos comprobar si existe una granja en el camino de un vértice $x$ a la raíz del camino heavy que contiene a $x$ ( $\texttt{root}[x]$ ) con el tipo de leche deseado en tiempo $\mathcal{O}(1)$ usando un mapa no ordenado. Nótese que solo necesitamos hacer dos operaciones upper_bound por consulta.

En la solución de abajo, me refiero a los tipos de leche como “colores”.

Implementación

Complejidad temporal: $\mathcal{O}(\log N)$ por consulta.

C++


#include <algorithm>
#include <iostream>
#include <map>
#include <unordered_map>
#include <vector>
 
/**
 * Description: Heavy-Light Decomposition, add val to verts
 * and query sum in path/subtree.
 * Time: any tree path is split into $\mathcal{O}(\log N)$ parts
 * Source: http://codeforces.com/blog/entry/22072,
 * https://codeforces.com/blog/entry/53170 Verification: *
 */
 
const int MX = 2e5 + 5;
int T[MX];
 
template <int SZ> struct HLD {
	int n, ti;
	int par[SZ], root[SZ], depth[SZ], sz[SZ], pos[SZ];
	std::vector<int> adj[SZ];
 
	std::map<int, int> all_of_col[SZ];
	std::unordered_map<int, int> first_cols[SZ];
 
	void add_edge(int x, int y) {
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
 
	void dfs_sz(int x) {
		sz[x] = 1;
		for (int &y : adj[x]) {
			par[y] = x;
			depth[y] = depth[x] + 1;
			adj[y].erase(find(std::begin(adj[y]), std::end(adj[y]), x));
			dfs_sz(y);
			sz[x] += sz[y];
			if (sz[y] > sz[adj[x][0]]) { std::swap(y, adj[x][0]); }
		}
	}
 
	void dfs_hld(int x) {
		pos[x] = ti++;
		all_of_col[T[x]][pos[x]] = depth[x];
		if (!first_cols[root[x]].count(T[x])) { first_cols[root[x]][T[x]] = depth[x]; }
 
		for (int &y : adj[x]) {
			root[y] = (y == adj[x][0] ? root[x] : y);
			dfs_hld(y);
		}
	}
 
	void init(int _n, int r = 0) {
		n = _n;
		par[r] = depth[r] = ti = 0;
		dfs_sz(r);
		root[r] = r;
		dfs_hld(r);
	}
 
	/** @returns the lowest common ancestor (LCA) of x and y */
	int lca(int x, int y) {
		for (; root[x] != root[y]; y = par[root[y]]) {
			if (depth[root[x]] > depth[root[y]]) { std::swap(x, y); }
		}
		return depth[x] < depth[y] ? x : y;
	}
 
	/** @returns depth of closest ancestor with desired color */
	int closest_ancestor(int x, int col) {
		while (x) {
 
			// check if there exists vertex above (or equal to x) in same heavy
			// path with desired color
			auto it = first_cols[root[x]].find(col);
 
			// if so, return its depth using upper_bound
			if (it != std::end(first_cols[root[x]]) && it->second <= depth[x]) {
				return std::prev(all_of_col[col].upper_bound(pos[x]))->second;
			}
			x = par[root[x]];
		}
		return -1;
	}
 
	bool exists(int x, int y, int col) { return closest_ancestor(x, col) >= depth[y]; }
};
 
void set_up(std::string name) {
	freopen((name + ".in").c_str(), "r", stdin);
	freopen((name + ".out").c_str(), "w", stdout);
}
 
HLD<MX> H;
 
int main() {
	set_up("milkvisits");
	int n, m;
	std::cin >> n >> m;
	for (int i = 0; i < n; i++) { std::cin >> T[i]; }
	for (int i = 0; i < n - 1; i++) {
		int x, y;
		std::cin >> x >> y;
		H.add_edge(--x, --y);
	}
 
	H.init(n);
	for (int i = 0; i < m; i++) {
		int a, b, c;
		std::cin >> a >> b >> c;
		int L = H.lca(--a, --b);
 
		// checks if color c is present on path from a to L, or b to L
		if (H.exists(a, L, c) || H.exists(b, L, c)) {
			std::cout << 1;
		} else {
			std::cout << 0;
		}
	}
}