# Matematical Transformation - Solución

https://codeforces.com/gym/103577/problem/G

Dado un árbol ernaizado en el nodo $1$ donde el valor inicial de cada nodo es $0$, procesar $Q$ queries, las cuales pueden ser de dos tipos:

1. Dado un nodo $u$ y dos valores $k$ y $c$, sumar $d_{u,v}*k+c$ a todos los nodos $v$ en el subarbol de $u$, donde $d_{u,v}$ es la distancia de $u$ a $v$.
2. Dado dos nodos $u$ y $v$ imprimir la suma de los valores en el camino de $u$ a $v$.

## Solución
Definamos a $sum_u$ como la suma de los valores de los nodos en el camino de $u$ a la raíz. La respuesta de una query del tipo $2$ se puede expresar como $sum_u+sum_v-sum_{lca(u,v)}-sum_{p[lca(u,v)]}$, donde $lca(u,v)$ es el Lowest Common Ancester de $u$ y $v$, y $p[u]$ es el padre $u$ en el árbol.

Veamos cómo se modifica el valor de $sum_v$ en la query $1$, para un nodo $v$ en el subarbol de $u$. Observemos que se debe sumar el siguiente valor a $sum_v$:

$$
\sum_{a \in path(u,v)}(d_{u,a}*k+c)=\sum_{a}(d_{u,a}*k)+\sum_{a}c
$$
$$
= (\sum_{a}d_{u,a}*k)+(d_{u,v}+1)*c
$$

Notemos que $d_{u,v}=p_v-p_u$, donde $p_u$ es la profundidad del nodo $u$, por lo tanto:

$$
(\sum_{a}d_{u,a}*k)+(d_{u,v}+1)c=(\sum_{a}(p_a-p_u)k)+(p_v-p_u+1)c
$$
$$
= k(\sum_a p_a - \sum_a p_u) + (p_v - p_u + 1)c
$$
$$
= k(\sum_a p_a - (p_v - p_u + 1) p_u) + (p_v - p_u + 1) c
$$
$$
= (k\sum_a p_a) + (p_v - p_u + 1)(c-p_uk)
$$

Notar que en $\sum_a p_a$ estamos sumando todas las profundidades desde $p_u$ hasta $p_v$, por lo tanto:

$$
= (k\sum_{i=p_u}^{p_v} i) + (p_v - p_u + 1)(c-p_u k)
$$
$$
= (k(\frac{p_v(p_v+1)-p_u(p_u-1)}{2})) + (p_v - p_u + 1)(c-p_uk)
$$

Finalmente, desarrollemos toda la expresión y agrupemos los términos por el explonente de $p_v$:

$$
= \frac{k}{2}p_v^2 + (\frac{k}{2}-p_uk+c)p_v + (\frac{k}{2}p_u(p_u-1)+c(1-p_u))
$$

Podemos observar que $sum_v$ se puede expresar de la forma $A_vp_v^2+B_vp_v+C_v$. Los valores de $p_v^2$ y $p_v$ nunca se modifican durante las queries, ya que dependen sólo de la profundidad del nodo $u$. Por lo tanto, mantendremos los valores de $A_v$, $B_v$ y $C_v$, y los utilizaremos cuando querramos encontrar el valor de $sum_v$.

Ahora, la query $1$ consiste en sumar:

* $A_v += \frac{k}{2}$
* $B_v += \frac{k}{2}-p_uk+c$
* $C_v += \frac{k}{2}p_u(p_u-1)+c(1-p_u)$

en todos los nodos $v$ en el subarbol de $u$.

Podemos utilizar la técnica de aplanamiento de un árbol y un Fenwick Tree o Segment Tree para actualizar todos los valores de $A_v$, $B_v$ y $C_v$ en el subárbol de $u$.

Para evitar problemas de precisión cuando tenemos términos con $k/2$, se pueden multiplicar por $2$ los términos que se suma y al contestar la query se divide entre $2$.

Complejidad: $O(nlogn)$.