Trees with any number of children
In a binary tree every node has at most two children, kept in the fields left and right. Many trees have no such limit: a manager can have any number of people reporting to them, and a folder can hold any number of folders. A tree like this is called a general tree, and each of its nodes keeps a list of its children in place of the two fields.
The words root, parent, child, leaf and subtree mean the same as in a binary tree. The first problem uses them for the staff of a company.
A company has employees, numbered 1 to . Employee 1 is the general director, and every other employee has exactly one direct boss. The subordinates of an employee are everyone below them: the people who report to them, the people who report to those, and so on.
The first input line holds , and the second holds the direct bosses of employees . Print the number of subordinates of each employee, from 1 to .
Constraints
Sample · Input
5 1 1 2 3
Output
4 1 1 0 0
In the sample, employees 2 and 3 report to employee 1, employee 4 reports to 2 and employee 5 reports to 3. The company is a tree with employee 1 as the root, and the boss of an employee is that node's parent:
The subtree of an employee is that employee together with everyone below them. The subordinates are the other nodes of the subtree, so each answer is the size of a subtree minus 1. The subtree of employee 1 holds all five employees, and .
We could count every subtree separately, by visiting everyone below each employee in turn. That visits the same people many times: employee 4 is visited for employee 2 and again for employee 1. It is slowest when the company is a chain, in which each employee is the boss of the next. With 200,000 employees, the count for employee 1 visits 199,999 people, the count for employee 2 visits 199,998, and so on:
At roughly simple operations a second, that is about 200 seconds, and the time limit is one second.
The sizes can be computed without the repeated visits, because a subtree is its top node together with the subtrees of that node's children. Its size is therefore 1, for the top node, plus the sizes of the children's subtrees. Once the children's sizes are known, their parent's size takes one addition per child, so each size is worked out once and then used once, by the parent. In the sample:
In code this has the shape of the recursive height function of a binary tree, with a loop over the children in place of the two calls and a sum in place of the larger of two heights. The program first builds the list of children of every employee from the line of bosses:
input = sys.stdin.readline
def subtree_size(v):
size[v] = 1 # the employee
for child in children[v]:
size[v] += subtree_size(child) # the child's whole subtree
return size[v]
n = int(input())
bosses = list(map(int, input().split()))
children = [[] for _ in range(n + 1)]
for employee, boss in enumerate(bosses, 2):
children[boss].append(employee)
size = [0] * (n + 1)
subtree_size(1)
print(*(size[v] - 1 for v in range(1, n + 1)))The first two lines replace input with a faster way to read a line, which large inputs need. The lists have n + 1 entries so that employee v can use entry v. enumerate(bosses, 2) numbers the bosses from 2, because the first number on the line is the boss of employee 2.
A leaf has an empty list of children, so its loop does nothing and its size stays 1. That is the base case, and the function needs no test for a missing child. The function is called once for every employee, and its loops run times in total, once for every employee who has a boss, so the program takes time.
The program is not ready to submit, though. In a chain of 200,000 employees the calls nest 200,000 deep, and Python stops with an error after about 1,000 nested calls. The third part of this lesson replaces the recursion with a loop.
A tree given as a list of edges
Subordinates tells us the parent of every node. The other problems in this lesson do not. They give the number of nodes and a list of edges, where an edge is a pair of nodes that are joined, and the list names no root. Here is such a tree, which we use for the rest of the lesson. It has 7 nodes, numbered 0 to 6, and the edges (1, 0), (0, 2), (3, 1), (1, 4), (5, 2) and (5, 6).
Two nodes joined by an edge are neighbours, and node 1 has three of them: 0, 3 and 4. A list of edges forms a tree when it connects all the nodes and leaves exactly one path between any two of them, as this one does. From 3 to 6, for instance, the only path is 3, 1, 0, 2, 5, 6. AtCoder's problem statements and some of the drawings on this page say vertex for node.
To speak of parents and subtrees we choose a root ourselves, and any node will do. The parent of every other node is then its neighbour on the path to the root, and its other neighbours are its children. With node 0 as the root, as in the right half of the figure, node 1 has the parent 0 and the children 3 and 4, and node 6 has the parent 5 and no children.
Every node except the root is joined to its parent by one edge, and every edge is the parent edge of exactly one node, its end farther from the root. So a tree with nodes always has edges.
A walk that skips the node it came from
In code, the edges go into one list per node: neighbors[v] holds the neighbours of node v, so every edge is stored twice. For our tree, neighbors[1] is [0, 3, 4] and neighbors[5] is [2, 6].
A recursive function can walk the tree from the root. It moves from each node to its neighbours the way subtree_size moved to the children, with one change. The neighbours of a node include its parent, and a call that moved back to the parent would be sent down again, without end. So the function takes a second argument, the node the walk came from, and skips it. Every other neighbour is a child.
Skipping the parent is enough to visit every node exactly once. Reaching a node a second time would take a second path to it from the root, and a tree has only one.
The function below computes two values for every node. The depth of a node is the number of edges between it and the root, also called its level. A child is one edge deeper than its parent, so its depth is set before the walk moves to it. The child's size is known only after its call has returned.
def visit(v, parent):
size[v] = 1
for u in neighbors[v]:
if u != parent: # every other neighbour is a child
depth[u] = depth[v] + 1 # known before the child is visited
visit(u, v)
size[v] += size[u] # known once the child's call has returned
n = 7
edges = [(1, 0), (0, 2), (3, 1), (1, 4), (5, 2), (5, 6)]
neighbors = [[] for _ in range(n)]
for a, b in edges:
neighbors[a].append(b)
neighbors[b].append(a)
depth, size = [0] * n, [0] * n
visit(0, -1)
print(depth)
print(size)The root has no parent, so the first call passes −1, which is no node's number. The call on 0 moves to 1, and the call on 1 moves to 3. Node 3 has no neighbour other than node 1, where the walk came from, so its call returns with size 1. The program prints these two lists:
v belongs to node v. The root has depth 0 and a subtree of all 7 nodes.Each node is visited once, and the loops read each edge twice, once from each of its ends, so the walk takes time.
The walk step by step
Step through the walk on our tree. A node shows its size when its call returns. Then choose 5 as the root at the top of the widget. The edges stay the same, but node 2 is now a child of 5 and node 0 a child of 2, and the sizes change with the parents.
A walk without recursion
While the recursive walk visits a node, the calls for all the nodes above it are still open, so in a chain of 200,000 nodes the calls nest 200,000 deep. Python raises a RecursionError after about 1,000 nested calls. sys.setrecursionlimit raises that limit, but how deep the calls can then go depends on the version of Python: with the limit raised, Python 3.14 handles the chain and Python 3.9 crashes on it without an error message. So the programs in the rest of this lesson walk the tree with a loop.
For a loop it is enough to have the nodes in an order in which every parent comes before its children. Level by level is such an order, and we build it the way a breadth-first traversal does, with a list in the role of the queue. The list starts with the root. We go through it from the front, and for each node we append its children, its neighbours other than its parent, to the back and record the node as their parent.
A child is appended while its parent is being read, so the parent is already ahead of it in the list. Nothing is taken off the list, so at the end it holds every node. For our tree rooted at 0:
Read from the back, the list gives every child before its parent, which is what the sizes need. Every size starts at 1, and each node, taken from the back of the list, adds its size to the size of its parent:
When the loop reaches a node, all its children have already added their sizes to it, because they come later in the list. The size it passes to its own parent is therefore final. Here is Subordinates written this way:
input = sys.stdin.readline
def root_order(neighbors, root):
parent = [-1] * len(neighbors)
order = [root]
for v in order: # also reads the nodes appended below
for u in neighbors[v]:
if u != parent[v]:
parent[u] = v
order.append(u)
return parent, order
n = int(input())
bosses = list(map(int, input().split()))
neighbors = [[] for _ in range(n + 1)]
for employee, boss in enumerate(bosses, 2):
neighbors[boss].append(employee)
neighbors[employee].append(boss)
parent, order = root_order(neighbors, 1)
size = [1] * (n + 1)
for v in reversed(order): # from the back: children first
if parent[v] != -1:
size[parent[v]] += size[v]
print(*(size[v] - 1 for v in range(1, n + 1)))root_order appends to order inside a for loop over order. Python allows this: the loop goes on to the appended nodes and ends when it reaches the end of the list. The root keeps the parent −1, and the test parent[v] != -1 skips it in the second loop.
The program stores each boss and employee as an edge in both directions, so that root_order also fits the later problems, which give plain edges. Each node is appended once and each edge is read twice, so this walk takes time as well.
Values that come from the parent
Sizes are built from the children, so the loop read the order from the back. A value built from the parent is filled in from the front. Depth is a value of this kind, with depth[v] = depth[parent[v]] + 1. The next problem needs another.
A tree has nodes numbered 1 to , with node 1 as the root, and every node has a counter that starts at 0. Then operations run: operation adds to the counter of every node in the subtree of .
The input gives and , the edges as pairs , then the operations as pairs . Print every counter after all the operations, from node 1 to .
Constraints
Sample · Input
4 3 1 2 2 3 2 4 2 10 1 100 3 1
Output
100 110 111 110
The sample tree has node 2 below the root, and nodes 3 and 4 below node 2. The operations add 10 to the subtree of 2, 100 to the whole tree and 1 to node 3.
An operation on the root changes all counters. Carried out as stated, operations on the root of a tree with nodes make additions. One addition per operation is enough if each operation only records its amount at the node it names, in a list added.
An operation on reaches node when is itself or one of its ancestors, the nodes on the path from up to the root. So the final counter of is the sum of added over and its ancestors. The counter of the parent already holds the sum over the ancestors, so
and one pass over the order from the front fills in every counter. For the sample:
The program keeps both rows in one list: counter[p] += x records the amounts, and the pass over the order turns them into the final counters. When the pass reaches a node, its own entry still holds only the amount recorded there, and its parent's entry is already final.
input = sys.stdin.readline
def root_order(neighbors, root):
parent = [-1] * len(neighbors)
order = [root]
for v in order: # also reads the nodes appended below
for u in neighbors[v]:
if u != parent[v]:
parent[u] = v
order.append(u)
return parent, order
n, q = map(int, input().split())
neighbors = [[] for _ in range(n + 1)]
for _ in range(n - 1):
a, b = map(int, input().split())
neighbors[a].append(b)
neighbors[b].append(a)
counter = [0] * (n + 1)
for _ in range(q):
p, x = map(int, input().split())
counter[p] += x # recorded at p only
parent, order = root_order(neighbors, 1)
for v in order: # from the front: parents first
if parent[v] != -1:
counter[v] += counter[parent[v]]
print(*counter[1:])Every operation now costs one addition, and the pass costs one more for every node.
The diameter by two walks
The distance between two nodes is the number of edges on the path between them, and the diameter of a tree is the largest distance between two of its nodes, the number of edges on a longest path. This part finds it by measuring distances alone.
You get a tree of nodes numbered 1 to . Print its diameter.
The first input line holds , and each of the next lines holds an edge .
Constraints
Sample · Input
5 1 2 1 3 3 4 3 5
Output
3
The sample tree joins node 1 to 2 and 3, and node 3 to 4 and 5. The path 2, 1, 3, 5 has three edges and no path in this tree has four, so the answer is 3.
One walk gives the distance from its starting node to every other node: with the start as the root, the distance to a node is its depth. We could walk from every node and keep the largest distance seen. That is walks of about steps each, which comes to steps for 200,000 nodes. Two walks are enough:
- Walk from any node, and let be a node that is farthest from it.
- Walk from , and let be a node that is farthest from .
- The distance from to is the diameter.
On our tree the first walk starts at node 0:
The diameter is 5, the distance from 6 to 3, and the path between them is 6, 5, 2, 0, 1, 3. In code, each walk is root_order followed by one pass from the front, and the three steps are the last four lines of the program:
input = sys.stdin.readline
def root_order(neighbors, root):
parent = [-1] * len(neighbors)
order = [root]
for v in order: # also reads the nodes appended below
for u in neighbors[v]:
if u != parent[v]:
parent[u] = v
order.append(u)
return parent, order
def distances_from(neighbors, start):
parent, order = root_order(neighbors, start)
dist = [0] * len(neighbors)
for v in order: # from the front: parents first
if parent[v] != -1:
dist[v] = dist[parent[v]] + 1
return dist
n = int(input())
neighbors = [[] for _ in range(n + 1)]
for _ in range(n - 1):
a, b = map(int, input().split())
neighbors[a].append(b)
neighbors[b].append(a)
from_1 = distances_from(neighbors, 1)
a = max(range(1, n + 1), key=lambda v: from_1[v]) # a node farthest from node 1
from_a = distances_from(neighbors, a)
print(max(from_a)) # the distance from a to bmax with key returns the node whose distance is largest. On the sample the walk from node 1 finds , two edges away, and the walk from 4 finds node 2 at distance 3. Both walks take time.
Why the two walks find a longest path
Here is our tree drawn with its longest path, from 6 to 3, laid flat and the rest of the tree hanging from it in branches. Node 4 is the only branch, and it hangs from the path at node 1.
- a longest path, 5 edges
A branch reaches no farther from the node where it hangs than either end of the path does. The branch at node 1 is node 4, one edge from node 1, and the nearer end of the path, node 3, is also one edge from node 1. If the branch went one node deeper, the path from 6 to node 1 followed by the branch would have 6 edges, more than the longest path.
Now start the first walk at any node , and let be the node of the longest path nearest to . Going from to and then from to a node is one way to reach , though not always the shortest, so is no farther from than the distance from to plus the distance from to .
From , the farther end of the path is at least as far as any node. To reach a node in a branch, we go along the path from to the node where the branch hangs and then into it, and by the rule above the branch is no longer than the piece of the path from that node to the end on the far side from . The route from to the farther end passes through , so its distance from is exactly the distance from to plus the distance from to the end. So no node is farther from than the farther end of a longest path.
The farthest node the first walk finds is therefore that end, or a node in a branch that is exactly as far away, which the folded read shows to be the end of another longest path. The second walk starts at this end of a longest path, and no node is farther from it than the other end of the same path. So the largest distance the second walk measures is the diameter.
Deeper read: the argument in full
Let the longest path run from to . Suppose a branch hanging at a node of the path reached farther from than does. Then the branch followed by the piece of the path from to would be longer than the longest path. The same goes with and exchanged, so a branch reaches no farther from than either end.
For a starting node , the path node nearest to is itself when is on the path. Every route from to the path enters it at , because is itself or lies in a branch that hangs at , and a branch joins the path only there. So the distance from to the farther end is the distance from to plus the distance from to that end.
The first walk may still pick a node in a branch, if it is exactly as far from as that end. The branch then reaches exactly as far from the node where it hangs as the path reaches from to its end on the far side from . It reaches no farther by the rule for branches, and no less far, because otherwise would be closer to than that end is. Replacing that piece of the path by the branch gives a path of the same length that ends at .
On our tree this happens when the first walk starts at node 5. Nodes 3 and 4 are both four edges from 5, and if the walk picks 4, the longest path 6, 5, 2, 0, 1, 4 ends there.
Either way is an end of a longest path. Taking as the starting node, the same reasoning shows that no node is farther from than the other end of that path, so the largest distance the second walk measures is the diameter.
The farthest node from every node
The two ends that the walks find also give the largest distance from every node, which the next problem asks for.
You get a tree of nodes numbered 1 to . For every node, print its distance to the node farthest from it.
The first input line holds , and each of the next lines holds an edge .
Constraints
Sample · Input
5 1 2 1 3 3 4 3 5
Output
2 3 2 3 3
The path from to that the two walks find is a longest path, so by the argument of the last part no node is farther from a node than the farther of and . The farther of the two is itself a node, so the bound is reached, and the largest distance from is the larger of its distances to and :
The second walk measured from_a, the distances from . A third walk, from , measures from_b. On our tree and :
input = sys.stdin.readline
def root_order(neighbors, root):
parent = [-1] * len(neighbors)
order = [root]
for v in order: # also reads the nodes appended below
for u in neighbors[v]:
if u != parent[v]:
parent[u] = v
order.append(u)
return parent, order
def distances_from(neighbors, start):
parent, order = root_order(neighbors, start)
dist = [0] * len(neighbors)
for v in order: # from the front: parents first
if parent[v] != -1:
dist[v] = dist[parent[v]] + 1
return dist
n = int(input())
neighbors = [[] for _ in range(n + 1)]
for _ in range(n - 1):
a, b = map(int, input().split())
neighbors[a].append(b)
neighbors[b].append(a)
from_1 = distances_from(neighbors, 1)
a = max(range(1, n + 1), key=lambda v: from_1[v]) # one end of a longest path
from_a = distances_from(neighbors, a)
b = max(range(1, n + 1), key=lambda v: from_a[v]) # the other end
from_b = distances_from(neighbors, b)
print(*(max(from_a[v], from_b[v]) for v in range(1, n + 1)))On the sample the walks find and . Node 3 is one edge from 4 and two edges from 2, so its answer is 2, and the program prints 2 3 2 3 3.
The centres of a tree
A LeetCode problem asks which nodes make the best root.
You get a tree of nodes labelled 0 to as a list of edges. Any node can be chosen as the root, and the height of the rooted tree is the number of edges on its longest downward path. Return every node whose choice as root gives the smallest height, in any order.
Constraints
edges.length- The input is a tree
Sample 1 · Input
n = 4, edges = [[1,0],[1,2],[1,3]]
Output
[1]
Sample 2 · Input
n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output
[3,4]
This problem counts the height of a rooted tree in edges. With as the root, the height is the distance from to the node farthest from it, which is far[v]. The answer is therefore every node whose far value is the smallest, and these nodes are called the centres of the tree.
The centres lie in the middle of a longest path. On our tree that path is 6, 5, 2, 0, 1, 3:
far values. The centres are 2 and 0.A tree has one centre when its longest path has an even number of edges and two when the number is odd, as here. The folded read below gives the reason. In the second sample 0, 3, 4, 5 is a longest path, and the centres are 3 and 4.
The solution is the Tree Distances I program with the nodes numbered from 0 and a last step that returns every node v for which far[v] equals the smallest value in far.
Deeper read: the middle of a longest path
On a longest path of edges, the node that is edges from one end is edges from the other, and its far value is the larger of the two numbers. That is smallest in the middle of the path: at one node, with , when is even, and at two neighbouring nodes when is odd. A node off the path reaches both ends through the path node where its branch hangs, so it is farther from both than that node is. Its far value is larger than that node's, and it is not a centre.
The sum of the distances from every node
On our tree the distances from node 0 are 0, 1, 1, 2, 2, 2, 3, and they add up to 11. The next problem asks for this sum for every node.
You get a tree of nodes numbered 1 to . For every node, print the sum of its distances to all other nodes.
The first input line holds , and each of the next lines holds an edge .
Constraints
Sample · Input
5 1 2 1 3 3 4 3 5
Output
6 9 5 8 8
For node 1 of the sample the distances to nodes 2, 3, 4 and 5 are 1, 1, 2 and 2, and the sum is 6. LeetCode has the same task under the name Sum of Distances in Tree, with the nodes numbered from 0.
A walk from every node is too slow, as it was for the diameter. We avoid it by getting the sum for a node from the sum for its parent.
Take node 1 of our tree, a child of node 0. The paths from 0 to the nodes 1, 3 and 4 begin with the edge from 0 to 1, so these three nodes, the subtree of 1, are one edge closer to 1 than to 0. The paths from 1 to the other four nodes begin with the same edge, so those nodes are one edge farther from 1. The sum for node 1 is therefore .
From a parent's sum to a child's sum
The same holds for any node and its parent . Write ans[v] for the sum of the distances from . The size[v] nodes in the subtree of are one edge closer to than to , and the other n - size[v] nodes are one edge farther:
Three passes over the order solve the problem. A pass from the back computes the sizes, as in Subordinates. A pass from the front computes the depths, and their sum is the answer for the root. A last pass from the front applies the rule to every other node, whose parent has its answer by then. Finding the answer for every node in this way, by moving the root across one edge at a time, is called rerooting. For our tree:
input = sys.stdin.readline
def root_order(neighbors, root):
parent = [-1] * len(neighbors)
order = [root]
for v in order: # also reads the nodes appended below
for u in neighbors[v]:
if u != parent[v]:
parent[u] = v
order.append(u)
return parent, order
n = int(input())
neighbors = [[] for _ in range(n + 1)]
for _ in range(n - 1):
a, b = map(int, input().split())
neighbors[a].append(b)
neighbors[b].append(a)
parent, order = root_order(neighbors, 1)
size = [1] * (n + 1)
for v in reversed(order): # from the back: children first
if parent[v] != -1:
size[parent[v]] += size[v]
depth = [0] * (n + 1)
for v in order: # from the front: parents first
if parent[v] != -1:
depth[v] = depth[parent[v]] + 1
ans = [0] * (n + 1)
ans[1] = sum(depth) # the root's distances are the depths
for v in order:
if parent[v] != -1:
ans[v] = ans[parent[v]] - size[v] + (n - size[v])
print(*ans[1:])On the sample the program prints 6 9 5 8 8. Each pass does a fixed amount of work for every node, so the program takes time.
Deeper read: the sum over all pairs of nodes
The split of the nodes into the two sides of an edge also solves a problem that asks for a single number.
You get a tree of nodes numbered 1 to , every edge of length 1. Print the sum of over all pairs .
The first input line holds , and each of the next lines holds an edge .
Constraints
Sample 1 · Input
2 1 2
Output
1
Sample 2 · Input
4 1 2 1 3 1 4
Output
9
In the second sample node 1 is joined to 2, 3 and 4. The three pairs that include node 1 are 1 apart and the three pairs of outer nodes are 2 apart, so the total is .
With nodes there are about pairs, too many to measure one at a time. We count by edges instead. The distance between two nodes is the number of edges on their path, so the total is, for every edge, the number of pairs whose path uses that edge, added up. Removing the edge between a node and its parent splits the tree into the subtree of , with size[v] nodes, and the rest, with n - size[v] nodes. A path uses the edge when its ends are on different sides, so the edge lies on the paths of size[v] * (n - size[v]) pairs:
input = sys.stdin.readline
def root_order(neighbors, root):
parent = [-1] * len(neighbors)
order = [root]
for v in order: # also reads the nodes appended below
for u in neighbors[v]:
if u != parent[v]:
parent[u] = v
order.append(u)
return parent, order
n = int(input())
neighbors = [[] for _ in range(n + 1)]
for _ in range(n - 1):
a, b = map(int, input().split())
neighbors[a].append(b)
neighbors[b].append(a)
parent, order = root_order(neighbors, 1)
size = [1] * (n + 1)
total = 0
for v in reversed(order): # from the back: children first
if parent[v] != -1:
total += size[v] * (n - size[v]) # pairs whose path uses the edge above v
size[parent[v]] += size[v]
print(total)When the loop reaches v, the size of v is final, so the product can be added before v passes its size on. On our tree the six edges give . That is half of , the sum of the answers from the rerooting, because every pair is counted there once from each of its two ends.
Common mistakes
Reading each edge as a parent followed by its child.
- Where it breaks
- Take the edges
(1, 0),(2, 0)and(3, 0)with the root 0. Fillingchildren[a].append(b)for each edge(a, b)gives node 0 no children.subtree_size(0)then returns 1 without visiting another node, and node 0 is counted as having 0 nodes below it where it has 3. - The fix
- Store each edge in both directions, and find the parents by walking from the root.
Printing the largest distance of the first walk as the diameter.
- Where it breaks
- On the Tree Diameter sample the walk from node 1 finds a largest distance of 2, and the diameter is 3.
- The fix
- The first walk only finds one end of a longest path. Walk again from that end.
Swapping the two signs in the rerooting rule.
- Where it breaks
- Writing
ans[v] = ans[p] + size[v] - (n - size[v])prints6 3 7 4 4on the Tree Distances II sample, where the answer is6 9 5 8 8. - The fix
- Going from the parent to
v, thesize[v]nodes in the subtree ofvget closer, so they are subtracted, and the othern - size[v]nodes are added.
Recall A tree has the edges (0, 1), (1, 2) and (1, 3), and the distances from node 0 add up to 5. What does the rerooting rule give for node 1, and what is the diameter?
With 0 as the root, the subtree of node 1 holds the nodes 1, 2 and 3, so size[1] is 3 and is 4. Going from 0 to 1 brings three nodes one edge closer and takes one node one edge farther, which gives , the sum of the distances 1, 1 and 1 from node 1. For the diameter, a walk from node 0 ends at node 2 or node 3, two edges away, and a walk from node 2 finds nothing farther than 2 edges, so the diameter is 2.
One more diameter problem
Judge problems
- Longest Circular Road(opens the judge in a new tab) ↗
cities are joined into a tree by roads, and you build one more road between two cities of your choice. The new road closes a cycle, and you want that cycle to have as many roads as possible. The cycle is the new road together with the path the tree already has between the two cities, so the answer is the diameter plus 1.
Further reading
- USACO Guide, SilverIntroduction to Tree Algorithms(opens in a new tab)
The module this lesson follows: the vocabulary of trees, Subordinates solved by a recursive function, and a problem list that includes Tree Diameter and both Tree Distances problems.
- USACO Guide, GoldDP on Trees - Solving For All Roots(opens in a new tab)
A second solution to Tree Distances I, which keeps for every node the two longest paths down into its subtree and the longest path that leaves the subtree, then a list of problems that are solved by moving the root one edge at a time.
- Antti Laaksonen, free PDFCompetitive Programmer’s Handbook, chapter 14(opens in a new tab)
Tree traversal, the diameter both by two searches and by dynamic programming, and the longest path from every node.
- OI Wiki, in Chinese树的直径(opens in a new tab)
The two-search method with a full proof, the tree DP method, a note that the two searches fail when an edge has negative length, and the fact that all longest paths share one midpoint when every edge length is positive.
- Pat MorinOpen Data Structures, Chapter 6: Binary trees(opens in a new tab)
Defines depth, subtree and height for a rooted tree, computes a node’s size from its children’s sizes in section 6.1.1, and in section 6.1.2 explains why recursion on a tall tree can run out of stack and walks a tree level by level with a queue. Parts of this page adapt this chapter’s text, licensed CC BY 2.5 Canada (creativecommons.org/licenses/by/2.5/ca), with changed wording, examples and code.
