P5836 [USACO19DEC] Milk Visits S

Farmer John plans to build $N$ farms and connect them with $N-1$ roads, forming a tree (that is, all farms are reachable from each other, and there are no cycles). Each farm has one cow, whose breed is either Guernsey or Holstein. Farmer John has $M$ friends who often come to visit him. When friend $i$ visits, Farmer John and this friend will walk along the unique path from farm $A_i$ to farm $B_i$ (it is possible that $A_i = B_i$). Also, they can taste the milk from any cow on the path they travel. Since most of Farmer John’s friends are also farmers, they have a very strong preference for milk. Some friends only drink Guernsey milk, and the rest only drink Holstein milk. A friend will be happy only if, during their visit, they can drink the type of milk they prefer. For each friend, determine whether they will be happy after the visit.

The first line contains two integers $N$ and $M$. The second line contains a string of length $N$. If the cow on farm $i$ is a Guernsey cow, then the $i$-th character is `G`; if the cow on farm $i$ is a Holstein cow, then the $i$-th character is `H`. The next $N-1$ lines each contain two distinct integers $X$ and $Y$ ($1 \leq X, Y \leq N$), indicating that there is a road between farms $X$ and $Y$. The next $M$ lines each contain integers $A_i$, $B_i$, and a character $C_i$. $A_i$ and $B_i$ are the endpoints of the path that friend $i$ walks during the visit. $C_i$ is one of `G` or `H`, indicating whether friend $i$ likes Guernsey milk or Holstein milk.

Output a binary string of length $M$. If friend $i$ will be happy, then the $i$-th character is `1`; otherwise it is `0`.

Here, the path from farm 1 to farm 4 includes farms 1, 2, and 4. All these farms have Holstein cows, so the first friend will be satisfied, while the second friend will not. About subtasks: Test point $1$ is the sample. Test points $2\sim 5$ satisfy $N \le 10^3$, $M \le 2\cdot 10^3$. For $100\%$ of the testdata, $1 \leq N \leq 10^5$, $1 \leq M \leq 10^5$. Problem by: Spencer Compton. Translated by ChatGPT 5