Counting Good JOI Tours in IOI Country

In IOI Country there are (N) cities numbered from (0) to (N-1) and (N-1) bidirectional roads numbered from (0) to (N-2). Road (j\ (0\le j\le N-2)) connects city (U_j) and city (V_j). It is guaranteed that any city is reachable from any other city via these roads.\n\nEach city (i\ (0\le i\le N-1)) has a restaurant of a certain type denoted by (F_i):\n- (F_i = 0): Juice shop\n- (F_i = 1): Japanese omelette shop\n- (F_i = 2): Ice cream shop\n\nMs. Rie is planning a sightseeing tour called JOI Tour which visits three restaurants in the following order:\n1. Choose a city (i_0\ (0\le i_0\le N-1)) with a juice shop and start there.\n2. Visit the juice shop in (i_0).\n3. From (i_0), take the bus along the unique shortest path to a city (i_1\ (0\le i_1\le N-1)) that has a Japanese omelette shop.\n4. Visit the Japanese omelette shop in (i_1).\n5. From (i_1), take the bus along the unique shortest path to a city (i_2\ (0\le i_2\le N-1)) that has an ice cream shop.\n6. Visit the ice cream shop in (i_2) and end the journey.\n\nHowever, to keep the tour interesting, she wants the chosen cities (i_0, i_1, i_2) to satisfy the following condition: when traveling along the shortest path from (i_0) to (i_1) and then from (i_1) to (i_2), no road is used twice. In a tree, the unique shortest path from (i_0) to (i_1) and from (i_1) to (i_2) may share some roads if and only if (i_1) lies on the unique shortest path between (i_0) and (i_2). Hence, a JOI Tour ((i_0,i_1,i_2)) is considered good if:\n\n- (F_{i_0} = 0), (F_{i_1} = 1), and (F_{i_2} = 2), and\n- (i_1) lies on the unique simple path between (i_0) and (i_2) (i.e. (d(i_0,i_2) = d(i_0,i_1)+d(i_1,i_2))).\n\nThere are (Q) events. In the ((k+1))-th event ((0\le k\le Q-1)), you are given two integers (X_k) and (Y_k) (with (0\le X_k\le N-1) and (0\le Y_k\le 2)). When the event occurs, the restaurant type at city (X_k) is changed to (Y_k). After each event, you should immediately compute the number of good JOI Tours under the new configuration.\n\nYour task is to implement the following functions: (init(N, F, U, V, Q)), (change(X, Y)), and (num_tours()) so that after each change you can output the updated number of good tours.

inputFormat

The input is given as follows:\n\n- The first line contains an integer (N) denoting the number of cities.\n- The second line contains (N) integers (F[0], F[1], \ldots, F[N-1]) (each (0), (1), or (2)) indicating the restaurant type in each city.\n- The next (N-1) lines each contain two integers (U_j) and (V_j) ((0\le U_j,V_j\le N-1)) representing a bidirectional road.\n- The following line contains an integer (Q), the number of restaurant type change events.\n- Then (Q) lines follow, each with two integers (X_k) and (Y_k) representing an event where the restaurant at city (X_k) is changed to type (Y_k) (guaranteed to be different from its current type).\n\nAfter processing the initial configuration (before any events) and after each event, output the number of good JOI Tours.

outputFormat

Output (Q+1) lines. The first line contains the number of good JOI Tours for the initial configuration, and each of the next (Q) lines contains the updated number after each change event.

sample

4
0 1 2 0
0 1
1 2
1 3
2
3 2
0 1

1
0
0