Diverging Directions

Explicación

Primero, necesitamos dividir las consultas en dos tipos: las que nos requieren saltar a la raíz, y las que no lo requieren. Consideremos una consulta del camino más corto $u \rightarrow v$ .

Caso 1: $u$ es un ancestro de $v$

La solución óptima es que nuestro camino simplemente camine hacia abajo de $u$ a $v$ . Esto es equivalente a $\texttt{dist}(1 \rightarrow v) - \texttt{dist}(1 \rightarrow u)$ , donde $1$ es la raíz de nuestro árbol. Para responder estas consultas, usamos el método descrito en este editorial.

Caso 2: $u$ no es un ancestro de $v$

En este escenario, nuestro camino de $u$ a $v$ tiene la siguiente estructura.

Primero, recorremos hacia abajo hasta algún nodo en el subárbol de $u$
Usando la arista de retroceso en el nodo elegido, saltamos al nodo $1$ .
Finalmente, caminamos hacia abajo hasta el nodo $v$

Podemos usar el mismo código del caso 1 para calcular $\texttt{dist}(1 \rightarrow v)$ . Sin embargo, no queda del todo claro cómo deberíamos determinar el mejor nodo para elegir en el subárbol de $u$ desde el cual saltar. Sea el nodo al que recorremos hacia abajo $x$ . Entonces, el costo de usar el nodo $x$ para saltar a la raíz es:

\texttt{dist}(u \rightarrow x) + \texttt{back}[x]

Aquí, $\texttt{back}[x]$ se refiere al costo de saltar de $x$ a la raíz. Usando la misma idea del caso 1, podemos cambiar un poco nuestra expresión.

\texttt{dist}(1 \rightarrow x) + \texttt{back}[x] - \texttt{dist}(1 \rightarrow u)

La distancia de la raíz al nodo $u$ está fija aquí. Así, queremos encontrar el mejor valor de $\texttt{dist}(1 \rightarrow x) + \texttt{back}[x]$ dentro del subárbol de $u$ . Para hacer esto, usamos un tour de Euler para aplanar nuestro árbol, y luego usamos un árbol de segmentos con propagación perezosa para responder nuestras consultas.

Nuestro árbol de segmentos debe soportar adición de rango y mínimo de rango. Para más información sobre cómo implementarlo, consultar el módulo Actualizaciones de Rango Consultas de Rango.

Manejar actualizaciones

Si la arista que estamos actualizando va del nodo $u$ al nodo $1$ , entonces solo afecta el valor en nuestro árbol de segmentos para el nodo $u$ . Así, hacemos una actualización puntual sobre el nodo en cuestión.

En el caso de que la arista que estamos actualizando no vaya de algún nodo a la raíz, entonces cambia todos los valores dentro del subárbol que afecta. Sea la arista afectada la que conecta el nodo $u$ y el nodo $v$ , con diferencia de peso $w$ . Entonces, debemos hacer lo siguiente.

Cambiar las distancias en el subárbol de $v$ en $w$
Cambiar el valor de $\texttt{dist}(1 \rightarrow x) + \texttt{back}[x]$ en $w$

En mi código, esto se reduce a actualizar el árbol de Fenwick que maneja las distancias de la raíz a los nodos, y actualizar el árbol de segmentos que contiene el valor de $\texttt{dist}(1 \rightarrow x) + \texttt{back}[x]$ para cada nodo.

Implementación

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

C++


#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
// BeginCodeSnip{Lazy Segment Tree (from the module)}
template <class Info, class Tag> class LazySegtree {
  private:
	const int n;
	vector<Info> tree;
	vector<Tag> lazy;
 
	/** builds the segtree values in O(N) time */
	void build(int v, int l, int r, const vector<Info> &a) {
		if (l == r) {
			tree[v] = a[l];
		} else {
			int m = (l + r) / 2;
			build(2 * v, l, m, a);
			build(2 * v + 1, m + 1, r, a);
			tree[v] = tree[2 * v] + tree[2 * v + 1];
		}
	}
 
	/** applies update x to lazy[v] and tree[v] */
	void apply(int v, int l, int r, const Tag &x) {
		tree[v].apply(x, l, r);
		lazy[v].apply(x);
	}
 
	/** pushes lazy updates down to the children of v */
	void push_down(int v, int l, int r) {
		int m = (l + r) / 2;
		apply(2 * v, l, m, lazy[v]);
		apply(2 * v + 1, m + 1, r, lazy[v]);
		lazy[v] = Tag();
	}
 
	void range_update(int v, int l, int r, int ql, int qr, const Tag &x) {
		if (qr < l || ql > r) { return; }
		if (ql <= l && r <= qr) {
			apply(v, l, r, x);
		} else {
			push_down(v, l, r);
			int m = (l + r) / 2;
			range_update(2 * v, l, m, ql, qr, x);
			range_update(2 * v + 1, m + 1, r, ql, qr, x);
			tree[v] = tree[2 * v] + tree[2 * v + 1];
		}
	}
 
	Info range_query(int v, int l, int r, int ql, int qr) {
		if (qr < l || ql > r) { return Info(); }
		if (l >= ql && r <= qr) { return tree[v]; }
		push_down(v, l, r);
		int m = (l + r) / 2;
		return range_query(2 * v, l, m, ql, qr) +
		       range_query(2 * v + 1, m + 1, r, ql, qr);
	}
 
  public:
	LazySegtree() {}
 
	LazySegtree(int n) : n(n) {
		tree.assign(4 << __lg(n), Info());
		lazy.assign(4 << __lg(n), Tag());
	}
 
	LazySegtree(const vector<Info> &a) : n(a.size()) {
		tree.assign(4 << __lg(n), Info());
		lazy.assign(4 << __lg(n), Tag());
		build(1, 0, n - 1, a);
	}
 
	/** updates [ql, qr] with the arbitrary update chosen */
	void range_update(int ql, int qr, const Tag &x) {
		range_update(1, 0, n - 1, ql, qr, x);
	}
 
	/** @return result of range query on [ql, qr] */
	Info range_query(int ql, int qr) { return range_query(1, 0, n - 1, ql, qr); }
};
 
struct Tag {
	ll add = 0;
	void apply(const Tag &t) { add += t.add; }
};
 
struct Info {
	ll min_val = 1e18;
	void apply(const Tag &t, int l, int r) { min_val += t.add; }
};
 
/** @return result of joining nodes a and b together */
Info operator+(const Info &a, const Info &b) { return (a.min_val < b.min_val) ? a : b; }
// EndCodeSnip
 
// BeginCodeSnip{BIT (from the module)}
template <class T> class BIT {
  private:
	int size;
	vector<T> bit;
	vector<T> arr;
 
  public:
	BIT(int size) : size(size), bit(size + 1), arr(size) {}
 
	/** Sets the value at index ind to val. */
	void set(int ind, T val) { add(ind, val - arr[ind]); }
 
	/** Adds val to the element at index ind. */
	void add(int ind, T val) {
		arr[ind] += val;
		ind++;
		for (; ind <= size; ind += ind & -ind) { bit[ind] += val; }
	}
 
	/** @return The sum of all values in [0, ind]. */
	T pref_sum(int ind) {
		ind++;
		T total = 0;
		for (; ind > 0; ind -= ind & -ind) { total += bit[ind]; }
		return total;
	}
};
// EndCodeSnip
 
int main() {
	int n, q;
	cin >> n >> q;
 
	vector<array<int, 3>> edges(2 * n - 2);
	vector<vector<array<int, 2>>> adj(n);
	vector<int> back(n);
 
	for (int i = 0; i < n - 1; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		u--, v--;
		edges[i] = {u, v, w};
		adj[u].push_back({v, w});
	}
 
	for (int i = 0; i < n - 1; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		u--, v--;
		edges[n - 1 + i] = {u, v, w};
		back[u] = w;
	}
 
	// calculating Euler Tour indices and the distances from
	// the root of the tree to every other node
	vector<int> tin(n);
	vector<int> tout(n);
	int timer = 0;
	BIT<ll> bit(n + 1);
	const auto dfs = [&](int u, int p, auto &&self) -> void {
		tin[u] = timer++;
		for (const auto [v, w] : adj[u]) {
			if (v == p) { continue; }
			self(v, u, self);
			bit.add(tin[v], w);
			bit.add(tout[v] + 1, -w);
		}
		tout[u] = timer - 1;
	};
	dfs(0, -1, dfs);
 
	// initializing our segtree
	vector<Info> arr(n);
	for (int i = 0; i < n; i++) { arr[tin[i]] = {back[i] + bit.pref_sum(tin[i])}; }
	LazySegtree<Info, Tag> st(arr);
 
	for (int t = 0; t < q; t++) {
		int type;
		cin >> type;
		if (type == 1) {
			int i, w;
			cin >> i >> w;
			i--;
			auto &[u, v, prev_wt] = edges[i];
			if (v == 0) {
				// just need to update the value for best node to root val
				st.range_update(tin[u], tin[u], {w - prev_wt});
			} else {
				// need to update root to node path distances and also
				// have a constant increase for all distances going down
				st.range_update(tin[v], tout[v], {w - prev_wt});
				bit.add(tin[v], w - prev_wt);
				bit.add(tout[v] + 1, prev_wt - w);
			}
			prev_wt = w;
		} else {
			int u, v;
			cin >> u >> v;
			u--, v--;
 
			ll dist_u = bit.pref_sum(tin[u]);
			ll dist_v = bit.pref_sum(tin[v]);
			if (tin[u] <= tin[v] && tout[v] <= tout[u]) {
				cout << dist_v - dist_u << "\n";
			} else {
				const Info best = st.range_query(tin[u], tout[u]);
				cout << best.min_val - dist_u + dist_v << "\n";
			}
		}
	}
}