A rooted binary tree of N ( 1<=N<=1000000 ) nodes is given. You need to answer Q ( 1<=Q<=100000 ) queries.

Each q query contains two inputs : u val

In each query, You need to check whether a node of value val is present in the subtree of node u or not.

I know only a naive approach ( first creating an adjacency list using set STL for each node by finding the subtree of it and then check whether value val is present in the subtree of node u or not ) to this problem. And it is obvious that the solution doesn't fit for given N range.

Can anyone suggest a better approach to this problem ?