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