All Tracks Algorithms Graphs Depth First Search Problem

Strange City
Tag(s):

Algorithms, Depth First Search, Graphs, Medium

Problem
Editorial
Analytics

Anchal lives in a city which has \(N\)​ ice cream parlours. The city has \(N-1\) connections such that every ice cream parlour can be reached from every other ice cream parlour. Each parlour has only one type of ice cream with cost \(C_{i}\) for each \(1 \le i \le N\)​. Anchal has \(Q\)​ queries with each query specifying a city \(R\)​ and two integers \(X\) and \(Y\). In every query she wants to reach the same destination ice cream parlour \(D\).Anchal wants to calculate the number of cities from which she can start her journey and reach the destination city \(D\)​ along the shortest path between the source and the destination city such that city \(R\) lies in its path and the sum of ice creams for these three cities lie between \(X\)​ and \(Y\) (Both inclusive).

Note : City \(D\) , City \(R\) and the city from which Anchal starts are pairwise distinct.


INPUT FORMAT

  • First line consists of three space separated integers \(N\) , \(Q\) and \(D\) as described above 
  • Second line consists of \(N\) space separated integers with \(i^{th}\) integer denoting \(C_{i}\) as described above
  • Next \(N-1\) lines each consist of 2 space separated integers \(U\) and \(V\) denoting there is a bidirectional path from ice cream parlour \(U\) to \(V\) and vice versa
  • Each of the following \(Q\) lines contain three space separated integers \(IN_{1}\) , \(IN_{2}\) and \(IN_{3}\)  describing one query. Lets define \(last\) as the answer of the previous query (If its first query then \(last\) = 0). The parameters of the query can be calculated by : 
    • \(R=IN_{1} \oplus last\)
    • \(X=IN_{2} \oplus last\)
    • \(Y=IN_{3} \oplus last\)

where \({\oplus}\) is the symbol for logical XOR.


OUTPUT FORMAT

  • For each query, print the answer to it on a separate line


CONSTRAINTS

  • \(1 \le N,Q \le 10^5\)
  • \(1 \le D, R \le N\) and \(R \ne D\)
  • \(1 \le X,Y,C_{i} \le 10^{12}\)
  • \(X \le Y\)

SUBTASKS

  • For 10 Points : \(1 \le N,Q \le 100\)
  • For 20 Points : \(1 \le N,Q \le 1000\)
  • For 70 Points : Original Constraints
SAMPLE INPUT
6 5 1
1 5 2 4 6 4 
2 1
3 2
4 3
5 3
6 4
6 5 9
4 5 12
4 6 13
2 6 14
6 2 11
SAMPLE OUTPUT
0
1
0
4
4
Explanation

For the first query : R = 6 , X = 5 and Y = 9. Also , D=1. Clearly there is no node from which we can start and reach node 1 via  node 6. Hence ans is 0

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: Bash, 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, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

HourStorm #4

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?