Hướng giải: Tom và Jerry

Gọi ~D_r(u,v)~ là khoảng cách giữa hai đỉnh ~u~ và ~v~ trong cây màu đỏ và ~D_b(u,v)~ là khoảng cách giữa hai đỉnh ~u~ và ~v~ trong cây màu xanh. Giả sử rằng có một cạnh nối màu đỏ giữa hai đỉnh ~a-b~ và ~D_b(a,b) \ge 3~. Khi đó, ta dễ dàng nhận thấy rằng nếu Jerry đến được đỉnh ~a~ hoặc đến được đỉnh ~b~ thì Tom sẽ không bao giờ bắt được Jerry. Ta gọi các đỉnh ~a~ và ~b~ này là các "đỉnh đặc biệt".

Xét cây màu xanh với gốc tại đỉnh ~Y~. Một vài đỉnh của cây này là "đỉnh đặc biệt". Nếu Jerry đến được một trong các "đỉnh đặc biệt" này, trò chơi sẽ kéo dài vô tận. Vì ta đã xét các cặp đỉnh ~u-v~ với ~D_b(u,v) \ge 3~ nên chỉ còn lại các cặp đỉnh thuộc trường hợp ~D_b(u,v)=1~ hoặc ~D_b(u,v) = 2~. Từ đó, Jerry sẽ luôn luôn di chuyển ở các đỉnh thuộc cây con gốc ~Y~ có chứa đỉnh ~X~. Ngoài ra, điều kiện để Jerry đến được một đỉnh ~u~ mà không bị Tom bắt là ~D_b(Y,u) > D_r(X,u)~. Bài toán có thể được giải quyết bằng thuật toán DFS cơ bản.

Độ phức tạp: ~O(N)~