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 ith vertex.
Then n1 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
princemishra:
20210311 15:15:56
learn path queries on trees (Euler tour technique) 

urielguz33:
20200602 22:47:07
Why 0.602 seconds? Why not just leave it at 1 second? Last edit: 20200602 23:03:15 

abir_075:
20200511 19:13:51
i got wa for not considering c=0 and cin cout can cause tle . easily solvable using HLD. :D 

grey_rabb1t:
20200129 16:00:40
good Last edit: 20200129 16:00:53 

danos:
20190828 10:53:05
AC in one go


joe85123:
20190825 09:02:54
solved with HLD and offline queries, O(m*log^2n) Last edit: 20190825 11:34:03 

archvoid:
20190404 11:28:59
Last edit: 20190404 17:10:07 

win11905:
20180210 06:05:06
ez solve in one submission


mahilewets:
20170816 19:24:57
C++14 Clang 4.0 is OK with DFSrecursion.


vladimira:
20170214 08:41:45
Last edit: 20170315 10:45:37 
Added by:  lxyxynt 
Date:  20120817 
Time limit:  0.602s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 