All Tracks Data Structures Advanced Data Structures Segment Trees Problem

Don wants help
Tag(s):

Medium

Problem
Editorial
Analytics

Don has a rooted tree, consisting of N vertexes. Each tree vertex has a unique index (integer from 1 to N), and also has a unique value associated to it.

The root of Don's tree has index 1.

Also Don has Q pairs of integers: X and Y. For each pair X, Y Don wants to know the Yth largest value in the path from root to Xth vertex.Let this value be P. Finally,Don asks you to calculate S such that

S=f( (( P%100)+1)*2131669703889824641) ,where f(x) is number of divisors of x.

Your task is to write a program that answer the queries asked by Don.

INPUT

First line contains an integer representing N the number of vertexes. Next line contain n integers ,each representing the value(Ai) associated with each vertex from 1 to N. Next N - 1 lines contain two integers U and V each, which means that vertex U and V are connected to each other. Next line contains an integer Q, the number of Queries. Next Q lines contain 2 integers X and Y each as described in the problem statement. All X will be distinct

OUTPUT

For each query print the value of S in a new line

If Yth largest value does not exist then print -1 only in a new line.

Constraints

1<=N,Q<=100000

1<=Ai<=10^7

1<=X,Y<=10^6

Author-Akshay Vasandani

Tester-Akshay Vasandani

SAMPLE INPUT
7
23 1 24 5 172 32 27
1 2
2 3
3 4
2 5
5 7
1 6
3
4 3
2 2
6 3
SAMPLE OUTPUT
36
18
-1
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications