Having been frustrated all morning by code that times out on Tasks 8 and 9, I timed my Python code on my own computer, and discovered that it is taking its longest, by far, at the stage of loading the data! On my home machine, I see:
Task Data size (kB) Time (s)
7 20 0.1
8 394 50
9 600 144
The stage where I measure the tree takes 0.2s for Task 9. I conclude that I'm not timing out because my search is too slow!
Any hints as to how I could get the data-loading stage to move more speedily? I am current creating a dict (hash) of lists, with each key being a vertex and each list containing the vertex's neighbours.
[Update: I broke out the data handling section a bit more and discovered that it's not getting the data into memory, but the part where I construct my tree data structure. So I guess I need to think again about how I do that!]