Mine and Tree

Statement:

In her spare time, Mine enjoys game shows and mathematics. In particular, she really likes geometry and graph theory. Today, she is a participant on the popular game show GeomeTree, where contestants show off their mathematical skills by performing operations on a point in the 2D coordinate plane, all while on a tree. Mine is in it to win it!

Each contestant is given an undirected graph with N (1 ≤ N ≤ 105) vertices and N-1 edges such that there is a unique path between every pair of vertices - a tree. On each vertex of the tree, an operation is written on it. The operation may either be "rotate your point by θ (0 ≤ θ < 360) degrees counterclockwise around the origin", "translate your point by a vector (dx, dy) (-105 ≤ dx, dy ≤ 105), or "move the point towards (but not past) another point (p,q) (-105 ≤ p,q ≤ 105) such that the new distance between these points is P% (0 ≤ P < 100) of the old distance". Contestants perform M (1 ≤ M ≤ 105) rounds of queries on this tree. Each round, there are two possible queries the contestant needs to perform.

The first kind of query is when the contestant is given two vertices of the tree (u,v) (1 ≤ u,v ≤ N) and a point (x,y) (-105 ≤ x,y ≤ 105). The contestant has to move the point from vertex u of the tree to vertex v of the tree, performing every operation written on the vertices to the point they were given along the way (including the operations on vertices u and v). Operations are cumulative, and you have to perform the operations sequentially.

The second kind of query is when the operation on a tree changes. The new operation will still be either a rotation, translation, or moving operation in accordance with the constraints above.

The first place prize in the game show is unlimited riches along with a platinum pass to a love hotel for two. We know which prize Mine is really interested in. However, all the other contestants are writing programs to play this ridiculously difficult game show for them. Since Mine is in a huge pinch right now, she has hired you to help her win! You have no choice but to write a program that helps her, otherwise you will be blasted into pieces by Pumpkin!

Statement:

All the numbers in the input are integers.

The first line of input will have N and M, separated by a single space.

The next N lines will each have the operation of each vertex of the tree, in order from 1..N.

An operation is one of the following:

  • R θ - rotate by θ degrees operation
  • T dx dy - translate by (dx, dy) operation
  • M p q P - translate by (p, q) such that the new distance is P% of the original distance operation.

The next N-1 lines describe the graph. Each line is a pair of vertices which are connected by an edge in the graph. There will be no self-loops or duplicate edges, and it is guaranteed that the resulting graph is a tree.

The next M lines will describe the queries.

If the line begins with:

  • Q it will be followed by u v x y, indicating the first kind of query
  • U it will be followed by u and the new operation on vertex u, in the same format as above, indicating the second kind of query
Output:

For each Q query, output two space-separated real numbers, the final coordinates of the input point. Both of these numbers should be within an absolute or relative error of at most 10-6.

Example input 1:

1 1
M 4 4 75
Q 1 1 0 0
	
Example output 1:

1.000000 1.000000
	
Example input 2:

2 3
R 45
R 135
1 2
Q 1 1 100 100
Q 1 2 100 100
Q 2 2 100 100
	
Example output 2:

0.000000 141.421356
-100.000000 -100.000000
-141.421356 0.000000
	
Example input 3:

5 8
R 90
T 1 1
R 45
T 3 2
R 0
1 2
2 3
3 4
4 5
Q 1 1 0 0
Q 3 3 -4 9
U 5 R 180
Q 1 5 1 1
Q 5 1 1 1
U 2 T 3 -1
Q 2 3 3 5
Q 3 1 13 37
	
Example output 3:

0.000000 0.000000
-9.192388 3.535534
-1.585786 -3.414214
-3.121320 1.707107
1.414214 7.071068
-34.355339 -13.970563
	
Example input 4:

20 10
M 17799 86094 84
T 30788 -16797
M 52445 -47508 4
T 26532 51287
T -50591 96517
M 30308 -85463 63
T -12715 53304
R 98
R 175
M -87887 80937 50
T 97336 -1201
R 341
R 138
M 5953 -7108 94
M 54046 65569 12
M 73656 25913 73
M 77721 -53360 30
R 212
T 68308 -46135
R 168
20 18
5 18
1 18
11 5
8 11
12 18
19 1
16 1
10 16
13 19
17 12
3 13
7 16
14 17
2 5
9 1
15 3
4 5
6 20
Q 1 9 -94625 41969
Q 5 4 -36490 77405
Q 4 14 -22835 -22452
Q 3 12 69121 18026
Q 12 3 96668 -18244
U 12 R 167
Q 3 4 -36148 25858
U 14 M -50430 -4710 38
Q 1 19 -14698 -71595
Q 9 3 77136 -81565
	
Example output 4:

72072.373558 -55521.798455
-60549.000000 225209.000000
72334.627176 -67005.847616
-43561.121525 -43816.554934
51641.774285 -44852.076359
-54419.181070 93065.877003
58809.520000 -92499.760000
48861.404178 -46505.826597
	
Time and memory limit:

  • 5s
  • 256MB

Problem source: DMOJ