Tree Dynamic Programming¶
Dynamic programming can be used to calculate some information during a tree traversal.
Time Complexities¶
Not yet added
The number of nodes in its subtree¶
The subtree contains the node itself and all nodes in the subtrees of its children. so we can calculate the number of nodes recursively using the following code
Time complexity: $\Omicron(n)$
1 2 3 4 5 6 7 8 9 10 

Diameter¶
The Diameter of a tree is the maximum length of a path between two nodes.
Algorithm 1 (based on DP)¶
A general way to approach many tree problems is to first root the tree arbitrarily. After this, we can try to solve the problem separately for each subtree. Our first algorithm for calculating the diameter is based on this idea.
An important observation is that every path in a rooted tree has a highest point: the highest node that belongs to the path. Thus we can calculate for each node the length of the longest path whose heighest point is the node. One of those path corresponds to the diameter of the tree.
We calculate for each node $x$ two values:
 toLeaf(x): the maximum length of a path from x to any leaf
 maxLength(x): the maximum length of a path whose highest point is $x$

$f(x)$: Longest path starts from node $x$ and goes into its subtree.

$g(x)$: Longest path starts in subtree of $x$, passes through $x$ and ends in subtree of $x$
If for all nodes $x$, we take maximum of $f(x), g(x)$, then we can get the diameter.
Dynamic programming can be used to calculate the above values for all nodes in $\Omicron(n)$ time.
Implementation¶
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 

More General Implementation¶
with weighted edges
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 

Algorithm 2 (based on DFS)¶
Another efficient way to calculate the diameter of a tree is based on two depthfirst searches. First, we choose an arbitrary node $a$ in the tree and find the farthest node $b$ from $a$. Then, we find the farthest node $c$ from $b$. The diameter of the tree is the distance between $b$ and $c$.
How this works?¶
Not yet added
implementation¶
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 

resources¶
https://codeforces.com/blog/entry/20935