gistfile1.txt

# Balanced binary tree of height 2. Boring, I know...
node_count = 7
edges = [
	(0,1),
	(0,2),
	(1,3),
	(1,4),
	(2,5),
	(2,6)
]

class Node(object):
	def __init__(self):
		self.children = []
		self.parent = None
		self.height_memo = None

# Step 1: Turn our weird set of nodes and edges into a normal tree structure. O(n)
nodes = [Node() for i in xrange(node_count)]
for u,v in edges:
	nodes[u].children.append(nodes[v])
	nodes[v].parent = nodes[u]

# Step 2: Pick an arbitrary node and travel upward to find the root node. O(n)
root = nodes[4] # Chosen by fair dice roll
while root.parent is not None:
	root = root.parent

# Step 3: DFS. O(n)
def height(node):
	if node.height_memo is None:
		if len(node.children) == 0:
			node.height_memo = 0
		else:
			node.height_memo = 1 + max([height(child) for child in node.children])
	return node.height_memo

def max_path_length(node):
	if len(node.children) == 0:
		return 0

	# Case 1: the longest path doesn't pass through this node, so it must be
	# the longest path of one of the children.
	case_1 = max([max_path_length(child) for child in node.children])

	# Case 2: the longest path does pass through this node, so it must equal
	# height of tallest subtree + height of second-tallest subtree + 2	
	subtree_heights = sorted([height(child) for child in node.children])
	case_2 = subtree_heights[-1] + subtree_heights[-2] + 2
	
	return max([case_1, case_2])

print max_path_length(root)