(Analysis by Benjamin Qi)

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

$$q_t\equiv time_t[2]-time_t[1]-time_t[3]-time_t[4]\pmod{12}$$
only takes on the values zero or one, regardless of what moves Bessie makes.

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

$$q_t=\sum_{x=1}^N(-1)^{dist[x]}\cdot time_t[x] \pmod{12}.$$
Then
$$q_0=q_1+1=q_2=q_3+1=q_4=\cdots .$$
If all clocks point to twelve after traversing $t$ corridors, $q_t$ must equal zero. This implies that $q_0$ must equal either zero or one.

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;
}