Magical Tree Query

sagarthecoder SEC Intra Campus Programm...
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.


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)


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


1 2
3 1
1 3
2 2



Login to submit.


75% Solution Ratio
riyad000Earliest, Jun '20
steinumFastest, 0.1s
steinumLightest, 7.6 MB
steinumShortest, 758B
Toph uses cookies. By continuing you agree to our Cookie Policy.