Let $time_t[x]$ denote the reading on the clock at room $x$ after Bessie traverses $t$ corridors.

First consider the sample case. The quantity

Step 0:

    11
     |
     |
11--10--11

$q_0\equiv 10-11-11-11\equiv 1\pmod{12}$

Step 1:

    12
     |
     |
11--10--11

$q_1\equiv 10-12-11-11\equiv 0\pmod{12}$

Step 2:

    12
     |
     |
11--11--11

$q_2\equiv 11-12-11-11\equiv 1\pmod{12}$

Step 3:

    12
     |
     | 
12--11--11

$q_3\equiv 11-12-12-11\equiv 0\pmod{12}$

Step 4:

    12
     |
     | 
12--12--11

$q_4\equiv 12-12-12-11\equiv 1\pmod{12}$

Step 5:

    12
     |
     |
12--12--12

$q_5\equiv 12-12-12-12\equiv 0\pmod{12}$.

This can be generalized to trees of any form. Let $dist[x]$ denote the number of edges on the path from $x$ to the start vertex. So for the sample case, $dist[2]=0$ and $dist[1]=dist[3]=dist[4]=1$. Define

Conversely, when $q_0$ is equal to zero or one a solution can always be constructed. This can be proven with induction.

• The conclusion is true when $N=2$.
• Otherwise, let $r$ be a room other than $1$ that is adjacent to only one other. Repeatedly traverse the cycle $1\to r\to 1$ until the clock at $r$ points to $12$. Then never visit $r$ again, effectively removing it from the tree and decreasing $N$ by one.

This solution runs in $O(N)$ time because if starting from room $1$ is okay, then starting from any room that is an even distance from room $1$ is also okay. Of course, the bounds were low enough that $O(N^2)$ solutions received full credit as well.

Dhruv Rohatgi's code:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int N;
vector<int> edges[100000];
int d[100000];
int A[100000];
int s0,s1,n0,n1;
 
void dfs(int i,int depth,int par)
{
	d[i] = depth;
	for(int j=0;j<edges[i].size();j++)
		if(edges[i][j]!=par)
			dfs(edges[i][j],depth+1,i);
}
 
int main()
{
	freopen("clocktree.in","r",stdin);
	freopen("clocktree.out","w",stdout);
	int a,b;
	cin >> N;
	for(int i=0;i<N;i++)
		cin >> A[i];
	for(int i=1;i<N;i++)
	{
		cin >> a >> b;
		a--,b--;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	dfs(0,0,-1);
	for(int i=0;i<N;i++)
	{
		if(d[i]%2) s1 += A[i], n1++;
		else s0 += A[i], n0++;
	}
	if((s0%12) == (s1%12))
		cout << N << '\n';
	else if((s0+1)%12 == (s1%12))
		cout << n1 << '\n';
	else if((s0%12) == ((s1+1)%12))
		cout << n0 << '\n';
	else
		cout << 0 << '\n';
	return 0;
}