Skip to Content
CTRL K

Path Queries

Pista 1

¿Podrías resolver este problema si este árbol fuera solo un arreglo?

Pista 2

Podemos usar un tour de Euler para comprimir el árbol en un arreglo visitando cada nodo exactamente dos veces.

Pista 3

¿Puedes hallar un mapeo de intervalos del arreglo a caminos del árbol?

Solución

Explicación: CPH 18.2

A diferencia de la explicación de arriba, en vez de guardar el tamaño del subárbol, guardamos el índice derecho del subárbol para determinar los límites del subárbol de cada nodo.

Observemos que cuando actualizamos un nodo con valor A[s]A[s] a xx, la suma de la raíz al nodo para cada nodo de su subárbol aumenta en la diferencia x−A[s]x-A[s]. Usando ETT, esto es equivalente a una actualización de rango.

Podemos usar un Árbol de Fenwick que soporta incrementos/decrementos de rango y consultas puntuales en tiempo O(log⁡N)\mathcal{O}(\log N).

Al implementar la solución, recordemos que incrementar un rango [a,b][a, b] con un Árbol de Fenwick corresponde a las operaciones

upd(a,x) \text{upd}(a, x) upd(b+1,−x) \text{upd}(b+1, -x)

Implementación

Complejidad temporal: O((N+Q)log⁡N)\mathcal O((N+Q)\log N)

// CodeSnip{CPP Short Template}
 
/**
 * Author: Lukas Polacek
 * Date: 2009-10-30
 * License: CC0
 * Source: folklore/TopCoder
 * Description: Computes partial sums a[0] + a[1] + ... + a[pos - 1],
 * and updates single elements a[i],
 * taking the difference between the old and new value.
 * Time: Both operations are $O(\log N)$.
 * Status: Stress-tested
 */
 
struct FT {
	vector<ll> s;
	FT(int n) : s(n) {}
	void update(int pos, ll dif) {  // a[pos] += dif
		for (; pos < sz(s); pos |= pos + 1) s[pos] += dif;
	}
	ll query(int pos) {  // suma de valores en [0, pos)
		ll res = 0;
		for (; pos > 0; pos &= pos - 1) res += s[pos - 1];
		return res;
	}
};
 
const int mx = 2e5 + 1;
 
vi adj[mx];
int A[mx];
int st[mx];
int en[mx];
int timer = 0;
FT ft(mx + 1);
 
void dfs(int x, int p) {  // tour de Euler
	st[x] = timer++;
	for (const int &e : adj[x])
		if (e != p) dfs(e, x);
	en[x] = timer - 1;
}
 
int main() {
	setIO();
 
	int n, q;
	cin >> n >> q;
 
	for (int i = 1; i <= n; i++) cin >> A[i];
 
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
 
	dfs(1, 0);
 
	for (int i = 1; i <= n; i++) {
		ft.update(st[i], A[i]);
		ft.update(en[i] + 1, -A[i]);
	}
 
	for (int i = 0; i < q; i++) {
		int type, s;
		cin >> type >> s;
		if (type == 1) {
			int x;
			cin >> x;
			ft.update(st[s], x - A[s]);
			ft.update(en[s] + 1, -(x - A[s]));  // incrementar en 1
			A[s] = x;
		} else {
			cout << ft.query(st[s] + 1) << '\n';
		}
	}
}
Fundamentos