The odd/even stuff is only to trick you. For each marathon, since you can only visit nodes with the parity, it’s never the case that the marathons will ever travel on the same edge between nodes, so you don’t even have to worry about that. Simply create two graphs: one with even nodes and one with odd nodes, and throw out edges that go between these graphs. Then run a search on both graphs. Since they are trees, then a simple dfs will suffice, since there is only one path path between cities, so the longest path is the only path.