Help me for Milk Visits (code gets half the test cases right)

Hi, I need help debugging Milk Visits (USACO Silver 2019/Dec/3). Basically, what happens is my code works for around half the test cases, but gets the wrong answer for the other half.

My solution was a bit different from the official solution. Instead of doing connected components, I used prefix sums on the tree. I rooted the tree at node 1, and then for each node I stored in an array how many G’s and how many H’s you encounter on the path from 1 to that node. Then, for each path given in the input, I used that to find how many G’s or H’s are along that path. I then printed the answer based on whether this quantity was 0 or not 0.

Could someone please help me figure out where I went wrong? This is especially baffling to me because around half the test cases do work.

My Code

#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
#include <string>
#include <cstdio>
#include <cstring>
#include <algorithm>  
#include <math.h>
#include <numeric>
using namespace std;
using ll=long long;
using ull=unsigned long long;

vector<int> adj[100001];
int G[100001], H[100001];
string s;

void dfs(int x, int p){
  if (s[x]=='G') G[x]=G[p]+1, H[x]=H[p];
  if (s[x]=='H') G[x]=G[p], H[x]=H[p]+1;
  for (int y: adj[x]){
    if (y!=p) dfs(y, x);

int main() {
  ifstream cin("");
  int N, M;
  // cout<<s;
  for (int i=1; i<N; i++){
    int X, Y;
  G[0]=0, H[0]=0;
  dfs(1, 0);
  ofstream fout("milkvisits.out");
  for (int z=0; z<M; z++){
    int A, B;
    char C;
    int t;
    if (C=='G') t=abs(G[A]-G[B])+(int)(s[B]=='G');
    if (C=='H') t=abs(H[A]-H[B])+(int)(s[B]=='H');
    if (t>0) fout<<1;
    else fout<<0;

I’m pretty sure what goes wrong in your algorithm is that it cannot tell the difference between these two scenarios as demonstrated by this, albeit poor, drawing. With 4 and 6 being the queried route for a Holstein farmer.

Your algorithm always assumes Scenario B which causes it to get queries incorrect. Hopefully this clears things up, and if it doesn’t, I would be happy to answer any questions.


Oh I see, that makes sense. I totally missed that. Thanks for catching my mistake!