prithivMLmods/Coder-Stat

1<h2>Twin Trees Bros.</h2>2 3<p>4  To meet the demand of ICPC (International Cacao Plantation Consortium), you have to check whether two given <i>trees</i> are <i>twins</i> or not.5</p>6 7<center>8  <img src="https://judgeapi.u-aizu.ac.jp/resources/images/ICPCAsia2019_twin_trees_bros_1" width="400"/><br>9Example of two trees in the three-dimensional space.10</center>11 12<p>13The term <i>tree</i> in the graph theory means a connected graph where the number of edges is one less than the number of nodes. ICPC, in addition, gives three-dimensional grid points as the locations of the tree nodes. Their definition of two trees being <i>twins</i> is that, there exists a geometric transformation function which gives a one-to-one mapping of all the nodes of one tree to the nodes of the other such that for each edge of one tree, there exists an edge in the other tree connecting the corresponding nodes. The geometric transformation should be a combination of the following transformations:14</p>15 16<ul>17<li> translations, in which coordinate values are added with some constants,</li>18<li> uniform scaling with positive scale factors, in which all three coordinate values are multiplied by the same positive constant, and </li>19<li> rotations of any amounts around either $x$-, $y$-, and $z$-axes.</li>20</ul>21 22<p>23  Note that two trees can be twins in more than one way, that is, with different correspondences of nodes.24</p>25 26<p>27  Write a program that decides whether two trees are twins or not and outputs the number of different node correspondences.28</p>29 30<p>31  Hereinafter, transformations will be described in the right-handed $xyz$-coordinate system.32</p>33 34<p>35  Trees in the sample inputs 1 through 4 are shown in the following figures. The numbers in the figures are the node numbers defined below.36</p>37 38<center>39  <img src="https://judgeapi.u-aizu.ac.jp/resources/images/ICPCAsia2019_twin_trees_bros_2" width="640"/>40</center>41 42<p>43  For the sample input 1, each node of the red tree is mapped to the corresponding node of the blue tree by the transformation that translates $(-3, 0, 0)$, rotates $-\pi / 2$ around the $z$-axis, rotates $\pi / 4$ around the $x$-axis, and finally scales by $\sqrt{2}$. By this mapping, nodes #1, #2, and #3 of the red tree at $(0, 0, 0)$, $(1, 0, 0)$, and $(3, 0, 0)$ correspond to nodes #6, #5, and #4 of the blue tree at $(0, 3, 3)$, $(0, 2, 2)$, and $(0, 0, 0)$, respectively. This is the only possible correspondence of the twin trees.44</p>45 46<p>47  For the sample input 2, red nodes #1, #2, #3, and #4 can be mapped to blue nodes #6, #5, #7, and #8. Another node correspondence exists that maps nodes #1, #2, #3, and #4 to #6, #5, #8, and #7.48</p>49 50<p>51  For the sample input 3, the two trees are not twins. There exist transformations that map nodes of one tree to distinct nodes of the other, but the edge connections do not agree.52</p>53 54<p>55  For the sample input 4, there is no transformation that maps nodes of one tree to those of the other.56  </p>57 58<h2>Input</h2>59<p>60  The input consists of a single test case of the following format.61</p>62<pre>63$n$64$x_1$ $y_1$ $z_1$65.66.67.68$x_n$ $y_n$ $z_n$69$u_1$ $v_1$70.71.72.73$u_{n−1}$ $v_{n−1}$74$x_{n+1}$ $y_{n+1}$ $z_{n+1}$75.76.77.78$x_{2n}$ $y_{2n}$ $z_{2n}$79$u_n$ $v_n$80.81.82.83$u_{2n−2}$ $v_{2n−2}$84</pre>85 86<p>87  The input describes two trees. The first line contains an integer $n$ representing the number of nodes of each tree ($3 \leq n \leq 200$). Descriptions of two trees follow.88</p>89 90<p>91  Description of a tree consists of $n$ lines that give the vertex positions and $n - 1$ lines that show the connection relation of the vertices.92</p>93 94<p>95  Nodes are numbered $1$ through $n$ for the first tree, and $n + 1$ through $2n$ for the second tree.96</p>97 98<p>99  The triplet $(x_i, y_i, z_i)$ gives the coordinates of the node numbered $i$. $x_i$, $y_i$, and $z_i$ are integers in the range between $-1000$ and $1000$, inclusive. Nodes of a single tree have distinct coordinates.100</p>101 102<p>103  The pair of integers $(u_j , v_j )$ means that an edge exists between nodes numbered $u_j$ and $v_j$ ($u_j \ne v_j$). $1 \leq u_j \leq n$ and $1 \leq v_j \leq n$ hold for $1 \leq j \leq n - 1$, and $n + 1 \leq u_j \leq 2n$ and $n + 1 \leq v_j \leq 2n$ hold for $n \leq j \leq 2n - 2$.104</p>105 106 107<h2>Output</h2>108<p>109Output the number of different node correspondences if two trees are twins. Output a zero, otherwise.110</p>111 112 113<h3>Sample Input 1 </h3>114<pre>11531160 0 01171 0 01183 0 01191 21202 31210 0 01220 2 21230 3 31244 51255 6126</pre>127<h3>Sample Output 1</h3>128<pre>1291130</pre>131<h3>Sample Input 2 </h3>132<pre>13341341 0 01352 0 01362 1 01372 -1 01381 21392 31402 41410 1 11420 0 01430 2 01440 0 21455 61465 71475 8148</pre>149<h3>Sample Output 2</h3>150<pre>1512152</pre>153