Hi

I saw my contribution going down so I decided to write a decent blog, explaining super advanced stuff, funny enough, I don't have the knowledge nor have the patience to write such a blog, so I wrote this blog explaining some applications of Rerooting Technique. But I was tired and lazy so here is a not quite usable nor perfect blog for whoever likes the Rerooting Technique(me for instance).

Note that RT stands for Rerooting Technique, DP stands for Dynamic Programming, RHS stands for Right Hand Side of an equation, LHS stands for Left Hand Side of an equation. (I assumed the reader is familiar with basics of math, trees, DFS and BFS)

Also I recommend reading my previous blog $$$\texttt{before}$$$ reading the rest of this blog:

Online Query Based Rerooting Technique

I recently solved the following problem for second or third time (which I believe is a very classic problem):

Given a tree, calculate $$$\displaystyle \sum_{u, v} d^2(u, v)$$$ (where $$$u$$$ and $$$v$$$ are two vertices not necessarily distinct, and $$$d(u, v)$$$ is the distance from $$$u$$$ to $$$v$$$ in the given tree, also $$$d^2(u, v) = d(u, v) \cdot d(u, v)$$$).

Trivial solution is $$$O(n^2)$$$, where for each vertex $$$u$$$ we use BFS and calculate $$$d(u, v)$$$ for all $$$v$$$. Then we add up $$$d^2(u, v)$$$ for all $$$u$$$ and $$$v$$$. Now we try to solve the problem in $$$O(n)$$$.

One can solve this problem using 3-4 DPs (and potentially using RT), which is what we are going to talk about, and then extend it to death.

To solve this problem, we need the following fact ($$$a_i$$$-s are some variables, in this problem they are $$$d(u, v)$$$ for some $$$u, v$$$):

This fact says that if we know all the sums in the RHS we can find the sum in LHS with the aforementioned equation, which is pretty useful.

Now we can calculate three DPs for each vertex $$$u$$$ (also $$$v \in subree_u$$$) using the fact above:

• $$$dp_u = \sum_{v} d^2(u, v)$$$
• $$$sum_u = \sum_{v} d(u, v)$$$
• $$$size_u = \sum_{v} 1 = \text{size of }subtree_u$$$

One can simply calculate $$$sum_u$$$ and $$$size_u$$$. To calculate $$$dp_u$$$ we can do this(where $$$c \in children_u$$$):

• $$$dp_u = \sum_c dp_c + 2\sum_c sum_c + \sum_c size_c$$$

After that $$$dp_r$$$ where $$$r$$$ is the root is equal to $$$\sum_v d^2(r, v)$$$ where $$$v$$$ is any of the vertices. So if we do the same dp from all possible roots, then answer to the problem is the sum of $$$dp_r$$$ when $$$r$$$ is the root with $$$O(n^2)$$$ time complexity. However, one can realize that we can use RT to solve the problem in $$$O(n)$$$, and I'm not going through that.

Now we solved the last problem in $$$O(n)$$$, what do we do next? EXTEND IT TO DEATH:

You are given a tree, and a polynomial $$$P$$$ of degree at most $$$k$$$. Calculate $$$\sum P(d(u, v))$$$.

Again we can calculate $$$d(u, v)$$$ for all $$$u$$$ and $$$v$$$, then add up $$$P(d(u, v))$$$-s, overall time complexity will be $$$O(n^2k)$$$ if done properly. I would hope for a $$$O(nk^2)$$$ time complexity looking at the second solution of the previous problem.

First define:

• $$$P_0 = x^0$$$
• $$$P_1 = x^1$$$

$$$\;\;\vdots$$$

• $$$P_k = x^k$$$

It's quite trivial that if we could calculate $$$S_i = \sum_{u,v} P_i(d(u, v))$$$ for $$$0 \le i \le k$$$, then we can calculate $$$\sum_{u, v} P(d(u, v)) = a_0S_0+a_1S_1+\dots+a_kS_k$$$

Let's try to extend the fact we used in the second solution. We want to be able to calculate $$$P_i(x+1)$$$ using $$$P_j(x)$$$-s. If we were able to do so we could define $$$k+1$$$ dp-s and do the rest pretty much the same as the first problem. It's trivial we can calculate $$$P_i(x+1)$$$ using $$$P_j(x)$$$-s where $$$0 \le j \le i$$$, same can be said about $$$P_i(x-1)$$$:

$$$P_i(x+1) = (x+1)^i = C(i, 0)x^01^i + C(i, 1)x^11^(i-1) + \dots + C(i, i)x^i1^0$$$

So if we have some some integers $$$a$$$, then if we know $$$\sum_j P_i(a_j)$$$, we can calculate $$$\sum_j P_i(a_j+1)$$$, and $$$\sum_j P_i(a_j-1)$$$, so we can use this to first find all dp-s when tree is rooted at a vertex, then use RT and calculate dp-s for different roots as well, and so, problem solved in $$$O(nk^2)$$$.

This problem can be solved in $$$O(nk)$$$ as well, as nor mentioned in the comments section (thanks!). To do that we need to change the definition of $$$P_i$$$, we can achieve $$$O(nk)$$$ if we define $$$\displaystyle P_i(x) = x(x-1)\dots (x-i) = \prod_{j=0}^i x-j$$$, so we'll have $$$P_i(x+1) = \frac{P_i(x)(x+1)}{x-i}$$$. However I don't fully understand how we find $$$P(x)$$$ using $$$P_i$$$-s, but we can assume there's a mathematical equation we can use or something, idk.

Sorry for skipping many details, feel free to ask any questions and/or discuss and/or give any recommendation/opinion in the comments section.

Yet it's not enough extension, what if it wasn't a tree but another special graph, or a graph in general.