Official Editorial

Explanation

Intuitively, there's two main "phases" to this fight:

1. Where some nodes could either go black or white, and it's not yet clear.
2. All nodes can only turn black or white due to being blocked in by Fennec or Snuke.

As long as there's an uncolored node on the one and only path from node $1$ to node $N$, we're in phase 1. After that, the tree has been cut in two and every uncolored node can only reach one of the two colors.

Thus, it would make sense for both players to try and get as many nodes on the path converted to their color before doing anything else. This winds up with the path split into half-black and half-white, with odd-length paths giving one extra black node since Fennec goes first.

After this, it's only a matter of seeing which player has staked out more territory, since they're the one that can make more moves and outlast their opponent.

Implementation

Time Complexity: $\mathcal{O}(N)$

Copy
#include <functional>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

int main() {
	int node_num;

Copy
import java.io.*;
import java.util.*;

public class FennecVSSnuke {
	private static List<Integer>[] neighbors;
	private static int[] parents;
	private static int[] colors;
	private static int diff = 0;  // fennec - snuke

	public static void main(String[] args) throws IOException {

Copy
from sys import setrecursionlimit

setrecursionlimit(10**8)


def calc_parents(at: int, parent: int):
	parents[at] = parent
	for n in neighbors[at]:
		if n != parent:
			calc_parents(n, at)