Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Magical Tree Query

By sagarthecoder · Limits 1s, 512 MB

You are given a rooted tree (a connected graph with no cycles) with n vertices. The vertices are numbered from 1 to n, the root is the vertex number 1. Each vertex i has an integer color Ci.

In this problem, you need to answer q queries. Each query we will ask you to perform the following operation:
u v : ask for how many numbers are divisible by 3 from common vertices between Subtree-u and Subtree-v.

Subtree of a node is a part of tree consisting of this node and all it’s descendants (direct or not). In other words, subtree of node p is formed by nodes s, such that node p is present on the path from s to root.

Input

The first line contains a single integer n (2 ≤ n ≤ 105) — the number of vertices in the tree. Each of next n lines contains a single integer color. The ith line contains the integer color Ci(1 ≤ Ci≤ 109) of ith node.

The next n-1 lines contain the edges of the tree. The ith line contains the numbers ai,bi (1 ≤ ai, bi≤ n; ai ≠ bi) — the vertices connected by an edge of the tree.
The next line contains a single integer q— the number of queries.
Each of next q lines contains two integers u, v (1 ≤ u, v ≤ n)

Output

Print q integers — the answers to the queries in the order the queries appear in the input

Sample

InputOutput
3
3
5
9
1 2
3 1
2
1 3
2 2

1
0

Discussion

Statistics


NaN% Solution Ratio

Submit

Login to submit

Related Contests

SEC Intra Campus Programming Contest, CSE Fest 2020 Ended at 2020-02-19 11:02:00 +0000 UTC