## Introduction

In this problem, we will solve the most exciting topics of competitive programming, i.e., Trees and Dynamic Programming.

Both Trees and DP fulfill the void of the data structures and algorithms.

Dynamic Programming is used to solve optimization problems, while trees are the hierarchical data structure having nodes connected by edges.

Ready for the problem statement??

## Problem Statement

Here we have to find the sum of the length of paths from it to all other nodes, using the Tree Rerooting technique in an undirected tree.

Before heading towards the approach, let's see what this problem looks like.

**What do you mean by the Tree Rerooting technique?**

Re-Rooting is a technique where we have to find a solution resulting from any chosen roots. We first see the solution to some fixed node and then start building the solution by rerooting the tree on all other nodes. It is a Dynamic Programming technique on trees.

Let us understand the problem with the help of an example.

**We are provided with a tree having '7' nodes.**

.

Here arrows represent the path. The tree is undirected.

**Output:**

12 9 17 14 10 15 15

**Explanation:**

**Node1: **sum of the path for every node is 0(length of node 1)+ 1(length of node 2)+ 1(length of node 3)+ 2(length of node 5)+ 2(length of node 4)+ 3(length of node 7)+ 3(length of node 6) = 12.

**Node2:** sum of the path for every node is 0(length of node 2)+ 1(length of node 1)+ 2(length of node 3)+ 1(length of node 5)+ 1(length of node 4)+ 2(length of node 7)+ 2(length of node 6) = 9

**Node3:** sum of the path for every node is 0(length of node 3)+ 1(length of node 1)+ 2(length of node 2)+ 3(length of node 5)+ 3(length of node 4)+ 4(length of node 7)+ 4(length of node 6) = 17.

**Node4:** sum of the path for every node is 0(length of node 4)+ 1(length of node 2)+ 2(length of node 1)+ 3(length of node 3)+ 2(length of node 5)+ 3(length of node 7)+ 3(length of node 6) = 14.

**Node5:** sum of the path for every node is 0(length of node 5)+ 2(length of node 1)+ 3(length of node 3)+ 2(length of node 4)+ 1(length of node 2)+ 1(length of node 7)+ 1(length of node 6) = 10.

**Node6:** sum of the path for every node is 0(length of node 6)+ 1(length of node 5)+ 2(length of node 2)+ 3(length of node 4)+ 3(length of node 1)+ 4(length of node 3)+ 2(length of node 7) = 15.

**Node7:** sum of the path for every node is 0(length of node 7)+ 1(length of node 5)+ 2(length of node 6)+ 2(length of node 2)+ 3(length of node 4)+ 3(length of node 1)+ 4(length of node 3) = 15.

We will be solving this problem using two approaches in the Java language.