Codeforces Round #291 Div. 2 E - Darth Vader and Tree

Problem Statement:
514E - Darth Vader and Tree

Solution:
Learnt something new! A very clever idea to use fast matrix exponentiation to solve for the DP states. Check the official editorial for a better understanding :) (Thank you for the enlightenment!)

Let V(m) be the number of vertices that are located exactly m unit distance away from root. Hence we can have the following relationship: \(V(m) = \sum_{i=0}^{100} c[i] V(m-i) \), where c[i] is the number of edges with length i amongst the n edges. What we want to find is \(S(x) = \sum_{i=0}^{x} V(x) \). The clever idea is to transform these equations into matrix multiplications!

a bit of matrix: LUP Decomposition

Scratch note:

Given system of linear equation \(Ax = b\), solve for \(x\).

One of the method to solve this classic linear algebra is described here called "LUP decomposition". LUP is itself an abbreviation for Lower, Upper, and Permutation Matrixes. The idea is that in a Gauss Elimination process, we are actually trying to transform a matrix into its row equivalent upper or lower triangular matrix. The method here owes to the insight from Gauss Elimination.

Recursively:

1. We swap the first row in \(A\) with another row such that the first element in \(A\) is not zero. Call this permutation \(Q\), and hence the resulting matrix \(QA\).
2. Rewrite QA as
\( \left(
\begin{array}{cc}
1 & 0 \\
v/a_{k1} & I_{n-1}
\end{array}
\right)

\left(
\begin{array}{cc}
a_{k1} & w^T \\
0 & A - vw^T/a_{k1}
\end{array}
\right)
\)

3. Let \(P =
\left(
\begin{array}{cc}
1 & 0 \\
0 & P'
\end{array}
\right)
Q
\)
Where \(P'(A-vw^T/a_{k1})=L'U'\)
Hence we have
\(PA =

\left(
\begin{array}{cc}
1 & 0 \\
0 & P'
\end{array}
\right)

\left(
\begin{array}{cc}
1 & 0 \\
v/a_{k1} & I_{n-1}
\end{array}
\right)

\left(
\begin{array}{cc}
a_{k1} & w^T \\
0 & A - vw^T/a_{k1}
\end{array}
\right)
\)

which simplifies to
\(PA =
\left(
\begin{array}{cc}
1 & 0 \\
v/a_{k1} & L'
\end{array}
\right)

\left(
\begin{array}{cc}
a_{k1} & w^T \\
0 & U'
\end{array}
\right)
\)
Or \(PA = LU\)