Farmer John is planning to build \(N\) (\(1 \leq N \leq 10^5\)) farms that will be
connected by \(N-1\) roads, forming a tree (i.e., all farms are reachable from
each-other, and there are no cycles). Each farm contains a cow with an integer
type \(T_i\) between \(1\) and \(N\) inclusive.

Farmer John's \(M\) friends (\(1 \leq M \leq 10^5\)) often come to visit him. During
a visit with friend \(i\), Farmer John will walk with his friend along the unique
path of roads from farm \(A_i\) to farm \(B_i\) (it may be the case that
\(A_i = B_i\)). Additionally, they can try some milk from any cow along the path
they walk. Since most of Farmer John's friends are also farmers, they have very
strong preferences regarding milk. Each of his friends will only drink milk from
a certain type of cow. Any of Farmer John's friends will only be happy if they
can drink their preferred type of milk during their visit.

Please determine whether each friend will be happy after visiting.

Problem credits: Spencer Compton

SCORING

• Test case 2 is the second example case below.
• Test case 3 satisfies \(N\le 10^3, M\le 2\cdot 10^3\).
• Test cases 4-7 satisfy \(C_i\le 10\) (\(C_i\) defined below).

Problem credits: Spencer Compton

The first line contains two integer \(N\) and \(M\).

The second line contains \(N\) space-separated integers \(T_1,T_2,\ldots, T_N.\) The
type of the cow in the \(i\)-th farm is denoted by \(T_i.\)

The next \(N-1\) lines each contain two distinct integers \(X\) and \(Y\)
(\(1 \leq X, Y \leq N\)), indicating that there is an edge between farms \(X\) and
\(Y\).

The next \(M\) lines contain integers \(A_i\), \(B_i\), and \(C_i\). \(A_i\) and \(B_i\)
represent the endpoints of the path walked during friend \(i\)'s visit, while
\(C_i\) (\(1\le C_i\le N\)) indicates the type of cow whose milk the friend enjoys
drinking.

Print a binary string of length \(M.\) The \(i\)th character of the string should be
'1' if the \(i\)th friend will be happy, or '0' otherwise.

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > December > Gold