BTCODE_G  Coloring Trees
Nivash and Bhoopathi play a game of memory, which goes as follows: There is a tree containing 'N' nodes, all of which are initially uncoloured. In the game, Nivash has 2 moves:
1) Command: Color a particular node with a given color.
2) Query: Ask Bhoopathi if the path from node 'a' to node 'b' (both inclusive), is monochromatic or not.(i.e Whether all nodes on the path have the same color).
Nivash can do these steps in any order he wishes and he colors each node atmost once. Whenever Nivash puts forth a 'Query' at Bhoopathi, Bhoopathi has to recollect the colouring of the tree and reply either "YES" or "NO". Can your help Bhoopathi answer these queries?
Input
The first line of input contains an integer 'N', denoting the number of nodes in the tree. The next 'N1' lines contain 2 space separated integers 'u' and 'v', denoting an edge between vertex 'u' and vertex 'v'.
The next line contains an integer 'Q', denoting the number of inputs (commands and queries) which Nivash wants to give. The next 'Q' lines contain 3 space separated integers 'x', 'a', 'b'. If 'x' is 1, it denotes a command to color node 'a' with a color 'b'. If 'x' is 2, it denotes a query and Bhoopathi should answer if the path from node 'a' to node 'b' (both inclusive), is monochromatic or not.
All vertices of the tree are 0 based.
Output
For each query, output "YES" or "NO" (quotes for clarity), denoting whether the path from node 'a' to node 'b' (both inclusive), is monochromatic or not.
Output "NO", even if all nodes on the path from node 'a' to node 'b' (both inclusive) are uncolored.
Example
Input: 3 0 1 1 2 7 1 0 11 2 0 1 2 0 2 1 2 12 1 1 11 2 0 1 2 0 2 Output: NO NO YES NO Constraints: 1 <= N <= 100000 1 <= Q <= 200000 1 <= color value <= 30.
Explanation:
Initially node '0' is colored with color '11', so path between node '0' and node '1' is not monochromatic. Hence, the answer is "NO". The same explanation holds for the path between node '0' and node '2'. Then node '2' is colored with color '12' and node '1' with color '11'. Now, all nodes on the path between node '0' and node '1' are colored with only one color ('11'), so the answer is "YES". The path between node '0' and node '2' has 2 colors ('11' and '12'), hence the answer is "NO".
hide comments
DK...:
20190418 02:27:59
I got AC with a simple hld 

kshubham02:
20181022 12:19:02
O(Q lg^2 N) fails with fast I/O. Is there any way to optimise HLDbased approach? 

spojabhi:
20180619 16:58:17
use simple DSU :} 

sifat_15:
20180520 16:52:50
AC in one go! Just figure out Which method should be used! Last edit: 20180520 16:53:11 

julkas:
20171203 12:45:34
Great problem. I suggest also https://www.hackerrank.com/challenges/kunduandtree/problem Last edit: 20171209 12:44:51 

Rezaul H Sagar:
20171001 17:10:07
how to optimize HLD? 

yogahmad:
20170803 14:57:44
very strict time limit, even HLD solution gives TLE.


siddharth_0196:
20170610 20:06:56
Last edit: 20170610 20:30:33 

conquistador:
20170517 22:01:13
@siddharth @ganda @mohit @banka optimise in every way possible to get AC . I got with 0.36 

shubham2305:
20170512 14:35:42
Time limit got strict. I earlier got AC with 0.35 sec but now TLE 
Added by:  suhash 
Date:  20110226 
Time limit:  0.207s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Bytecode 2011, NIT Trichy, India 