Omsk Metro (hard version)

Análisis oficial 

Explicación

Podemos lograr la suma $k_i$ en el camino de $u_i$ a $v_i$ sii la suma máxima de un segmento en el camino es mayor o igual que $k_i$ y la suma mínima de un segmento en el camino es menor o igual que $k_i$. Esto se debe a que todos los $x_i \in \{-1, 1\}$, así que cualquier ajuste desde el segmento de suma máxima hasta el segmento de suma mínima cambiará la suma exactamente en $1$. Por esto, podemos obtener todos los valores $[\texttt{fullMin}_{u_i, v_i}, \texttt{fullMax}_{u_i, v_i}]$ en el camino $(u_i, v_i)$ donde $\texttt{fullMax}_{u_i, v_i}$ y $\texttt{fullMin}_{u_i, v_i}$ denotan las sumas máxima y mínima de un segmento en el camino $(u_i, v_i)$.

Para hallar $\texttt{fullMax}_{u_i, v_i}$ y $\texttt{fullMin}_{u_i, v_i}$ para algún camino $(u_i, v_i)$, podemos hacer lo siguiente. Para cada subsegmento de un camino, podemos guardar además la suma mínima de un prefijo, la suma máxima de un prefijo, la suma mínima de un sufijo, la suma máxima de un sufijo y la suma total. Llamemos a estos $\texttt{prefixMin}_{u_i, v_i}$, $\texttt{prefixMax}_{u_i, v_i}$, $\texttt{suffixMin}_{u_i, v_i}$, $\texttt{suffixMax}_{u_i, v_i}$ y $\texttt{sum}_{u_i, v_i}$ para el camino $(u_i, v_i)$.

Fusionemos dos caminos: $(u_i, v_i)$ y $(u_j, v_j)$. Denotemos el camino resultante como $(u_i, v_j)$. Podemos observar que $\texttt{fullMax}_{u_i, v_j}$ y $\texttt{fullMin}_{u_i, v_j}$ pueden ser equivalentes a sus valores para uno de los subsegmentos, o su valor puede actualizarse a partir del sufijo de $(u_i, v_i)$ y el prefijo de $(u_j, v_j)$. Esto nos da las fórmulas:

A continuación, nuestro prefijo mínimo y máximo pueden ser los del camino $(u_i, v_i)$ o incluir los del camino $(u_j, v_j)$ sumados a $\texttt{sum}_{u_i, v_i}$. Esto se debe a que para incorporar el prefijo del segundo segmento, debemos tomar por completo el primero. Esto nos da las fórmulas:

Para hallar lo mismo para el sufijo, podemos usar un proceso similar. Podemos tomar el sufijo óptimo de $(u_j, v_j)$ o el de $(u_i, v_i)$ sumado a $\texttt{sum}_{u_j, v_j}$. Esto nos da las fórmulas:

Para $\texttt{sum}_{u_i, v_j}$, simplemente sumamos las sumas de $\texttt{sum}_{u_i, v_i}$ y $\texttt{sum}_{u_j, v_j}$:

Para resolver las consultas, podemos usar binary lifting. Podemos calcular nuestros valores para los caminos $(u_i, lca(u_i, v_i))$ y $(v_i, lca(u_i, v_i))$. Luego fusionamos estos caminos como se describió arriba y comprobamos si $\texttt{fullMin}_{u_i, v_i} \leq k_i \leq \texttt{fullMax}_{u_i, v_i}$.

Implementación

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

#include <bits/stdc++.h>
using namespace std;
 
struct station {
	int fullMin, fullMax, suffixMin, suffixMax, prefixMin, prefixMax, sum;
};
 
station add(station a, station b) {
	station res = {0, 0};
	res.sum = a.sum + b.sum;
 
	res.prefixMin = min(a.prefixMin, a.sum + b.prefixMin);
	res.prefixMax = max(a.prefixMax, a.sum + b.prefixMax);
 
	res.suffixMin = min(b.suffixMin, a.suffixMin + b.sum);
	res.suffixMax = max(b.suffixMax, a.suffixMax + b.sum);
 
	res.fullMin = min(res.fullMin, a.fullMin);
	res.fullMin = min(res.fullMin, b.fullMin);
	res.fullMin = min(res.fullMin, a.suffixMin + b.prefixMin);
 
	res.fullMax = max(res.fullMax, a.fullMax);
	res.fullMax = max(res.fullMax, b.fullMax);
	res.fullMax = max(res.fullMax, a.suffixMax + b.prefixMax);
	return res;
}
 
const int LOG = 19;
 
int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<vector<int>> lift(n + 1, vector<int>(LOG, -1));
		vector<vector<station>> dp(n + 1, vector<station>(LOG));
		vector<int> dist(n + 1, -1);
		dist[0] = 0;
		dp[0][0] = {0, 1, 0, 1, 0, 1, 1};
		int next = 1;
		while (n--) {
			char type;
			cin >> type;
			if (type == '+') {
				int parent, value;
				cin >> parent >> value;
				parent--;
				dist[next] = dist[parent] + 1;
				lift[next][0] = parent;
				dp[next][0] = {min(value, 0), max(value, 0), min(value, 0),
				               max(value, 0), min(value, 0), max(value, 0),
				               value};
				for (int i = 1; i < LOG; i++) {
					if (lift[next][i - 1] == -1) break;
					lift[next][i] = lift[lift[next][i - 1]][i - 1];
					dp[next][i] = add(dp[next][i - 1], dp[lift[next][i - 1]][i - 1]);
				}
				next++;
			} else {
				int u, v, k;
				cin >> u >> v >> k;
				u--;
				v--;
				if (dist[v] > dist[u]) swap(u, v);
				int difference = dist[u] - dist[v];
				station cur = {0, 0, 0, 0, 0, 0, 0}, cur2 = {0, 0, 0, 0, 0, 0, 0};
				for (int i = LOG - 1; i >= 0; i--) {
					if (difference < (1 << i)) continue;
					cur = add(cur, dp[u][i]);
					u = lift[u][i];
					difference -= (1 << i);
				}
				for (int i = LOG - 1; i >= 0; i--) {
					if (lift[u][i] == lift[v][i]) continue;
					cur = add(cur, dp[u][i]);
					cur2 = add(cur2, dp[v][i]);
					u = lift[u][i];
					v = lift[v][i];
				}
				cur = add(cur, dp[u][0]);
				if (u != v) {
					cur2 = add(cur2, dp[v][0]);
					u = lift[u][0];
					cur = add(cur, dp[u][0]);
				}
				swap(cur2.prefixMin, cur2.suffixMin);
				swap(cur2.prefixMax, cur2.suffixMax);
				cur = add(cur, cur2);
				cout << (k >= cur.fullMin && k <= cur.fullMax ? "YES\n" : "NO\n");
			}
		}
	}
	return 0;
}