GOT - Gao on a tree
There's a tree, with each vertex assigned a number. For each query (a, b, c), you are asked whether there is a vertex on the path from a to b, which is assigned number c?
Input
There are multiple cases, end by EOF.
For each case, the first line contains n (n <= 100000) and m (m <= 200000), representing the number of vertexes (numbered from 1 to n) and the number of queries.
Then n integers follows, representing the number assigned to the i-th vertex.
Then n-1 lines, each of which contains a edge of the tree.
Then m lines, each of which contains three integers a, b and c (0 <= c <= n), representing a query.
Output
You should output "Find
" or "NotFind
" for every query on one line.
Output a blank line AFTER every case.
Example
Input: 5 5 1 2 3 4 5 1 2 1 3 3 4 3 5 2 3 4 2 4 3 2 4 5 4 5 1 4 5 3 Output: NotFind Find NotFind NotFind Find
hide comments
aristofanis:
2014-02-06 19:21:22
Be careful! Got AC with C++ 4.0.0-8 and for some reason the same code compiled with C++ 4.3.2 gave me SIGSEGV! I think it has to do with the maximum stack size, as I am using recursion... |
|
Hussain Kara Fallah:
2013-05-24 05:30:32
for who solved this problem
|
|
:D:
2013-02-14 11:05:59
I used b) per test case. Hopefully exact judge isn't used and that's not a problem. |
|
Luke Pebody:
2013-02-14 09:22:56
What does "Output a blank line AFTER every case." mean in this case?
|
|
Buda IM (retired):
2012-10-06 13:01:45
0<=c<=n |
|
[Hakuna Matata]:
2012-09-18 05:03:06
Then n integers follows, representing the number assigned to the ith vertex.!!
|
|
lxyxynt:
2012-08-18 07:00:50
I'm sorry for my mistake..The dataset has the testcase number T, and i have deleted it and all submit has rejudged. |
|
Damian Straszak:
2012-10-05 21:31:07
getting SIGFPE on assertion "first vertex of edge" > n
|
|
Damian Straszak:
2012-08-17 19:28:39
please specify constraints on numbers assigned to vertices |
|
lxyxynt:
2012-10-05 21:31:52
@Diaa Thx for reminding! |
Added by: | lxyxynt |
Date: | 2012-08-17 |
Time limit: | 0.602s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |