Triplet Transitivity in the Number‐Picking Game on Trees

In this problem, a game called "Number-Picking" is played on a sequence of integers. A player starts with a sequence of n integers (written randomly on paper) and then, repeatedly, removes either the leftmost or rightmost number to form a new sequence S of length n. The score is computed as

$$P = S_1\times 5^0 + S_2\times 5^1 + \cdots + S_n\times 5^{n-1}, $$

and after converting P to binary, if the last three digits are 011 (i.e. if \(P \equiv 3 \pmod{8}\)), the game is won. A sequence is called a good sequence (良列) if and only if there is some removal order that produces a winning score (i.e. one congruent to 3 modulo 8); otherwise it is called a difficult sequence (刁列).

To make the game more interesting, the players decide to pre-write a large unrooted tree with m nodes, each node labeled with an integer. For any two nodes \(v_i\) and \(v_j\), the unique simple path between them defines a sequence (denoted as \(i\sim j\)) on which the game is played. Thus, each path (or sequence) is either good or difficult.

Small X conjectured a transitivity property for these sequences: for any three distinct nodes \(i \lt j \lt k\), the following should hold:

• If both \(i\sim j\) and \(j\sim k\) are good, then \(i\sim k\) must be good.
• If at least one of \(i\sim j\) or \(j\sim k\) is difficult, then \(i\sim k\) must be difficult.

This is equivalent to saying that for any triple \((i,j,k)\) with \(i\lt j \lt k\), $$G(i,k) = G(i,j)\land G(j,k),$$

where (G(u,v)=1) if the sequence (u\sim v) is good and (0) if it is difficult.

Your task is: Given the tree, determine the number of triples \((i,j,k)\) (with \(i \lt j \lt k\)) for which the above transitivity property holds.

Note on the Game: Since the score is computed as $$P = \sum_{r=1}^{n} S_r\times 5^{r-1},$$

and since (5^0 \equiv 1,; 5^1 \equiv 5,; 5^2 \equiv 1,; 5^3 \equiv 5) modulo 8, the multipliers alternate between 1 and 5 modulo 8. Therefore, when playing on a sequence (A = [a_1,a_2,\dots,a_n]), the removal order (i.e. choosing leftmost or rightmost) affects which multiplier is applied to each element. A sequence is good if there exists some removal order that produces a score (P) with (P \equiv 3 \pmod{8}>.

Input/Output: See the input and output descriptions below.

inputFormat

The input starts with a line containing a single integer m (the number of nodes in the tree). The next line contains m integers, where the i-th integer is the number written on node \(i\). Following this, there are m-1 lines each containing two integers \(u\) and \(v\) representing an undirected edge between nodes \(u\) and \(v\>.

outputFormat

Output a single integer, the number of triples \((i,j,k)\) with \(i \lt j \lt k\) for which the transitivity property G(i,k) = G(i,j) && G(j,k) holds. (Here, G(u,v) is 1 if the sequence from node \(u\) to node \(v\) is good and 0 if it is difficult.)

sample

5
1 2 3 4 5
1 2
2 3
3 4
4 5

1