Sam And Alien Attack

0

0 votes
Trie, Hard, xor, persistence
Problem

SAM is the chief of ALIEN BATTLE FORCE of MOFAZIA galaxy.Each planet in MOFAZIA galaxy has a unique id uid and a force strength fs associated with it and they are all connected with a pathway directly or indirectly .But their is something very weird with this galaxy , with time new planets are born and gets connected to some already existing planet with a pathway.And as it is obvious they are born with uid and fs.MOFAZIA galaxy has a planet capital and its uid and force strength will be given beforehand.

The aliens of outer galaxy are planning a battle against MOFAZIA. While fighting with aliens SAM needs a helper to do two kind of operations which must be done as soon as possible.

Operation type 1: given 'v' , 'u' and 'fs' connect a new planet with uid 'u' and force strength 'fs' to an already existing planet with uid as 'v'.
Operation type 2: given 'u' and 'c' find two values 'a' and 'b'.How to calculate a and b in 2nd operation is given below.

And for this he needs your help. HELP SAM ;).

Calculation of a and b:

  • a = x ,where x is the force strength of the planet that gives maximum value of 'c' xor 'x' on path from planet with uid as 'u' to capital planet of galaxy.
  • b = x ,where 'x' is the force strength of the planet that gives minimum value of 'c' xor 'x' on path from planet with uid as 'u' to capital planet of galaxy.

INPUT:

There is only one testcase in each file.
1st line contains two integers N and O , number of planets in the galaxy initially and number of operations to be handled by you.
2nd line contains two integers 'u' and 'k' , which are uid of capital planet and it's force strength respectively.
Each of the next N-1 lines contain 'u', 'v' and 'k' i.e. there is pathway between u and v and force strength of u is k.
Now each of the next line asks you to perform two of the given type of operation (either 1 or 2):

  • 1 v u fs
  • or
  • 2 u c

OUTPUT:

For each query of type 2 output the value of a and b on new line.

CONSTRAINTS:

  • 1 ≤ N ≤ 100000
  • 1 ≤ O ≤ 200000
  • 1≤ u,v,c,fs ≤ (2^31)-1
  • All ids are unique.
  • Whenever you have to connect a node u to another one v, it is guaranteed that v is already connected, directly of indirectly, to planet capital.

Time Limit: 2
Memory Limit: 256
Source Limit:
Editor Image

?