2241E.md (2341B)
1 Source: https://codeforces.com/problemset/problem/2241/E 2 3 E. Fair and Square 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 A tree is an undirected connected graph with no cycles. 22 23 You are given a tree having $n$ vertices. Each vertex $i$ has an integer value $a_i$ written on it. 24 25 For any two vertices $u$ and $v$ ($u \ne v$), define $p(u, v)$ as the product of the values written on the vertices lying on the unique simple path$^{\text{∗}}$ from $u$ to $v$. 26 27 An unordered triplet of three distinct vertices $\{u, v, w\}$ is called good if and only if: $p(u,v)\cdot p(v,w)\cdot p(w,u)$ is a perfect square. 28 29 Determine the number of good unordered triplets in the given tree. 30 31 $^{\text{∗}}$A simple path from the vertex $u$ to vertex $v$ is a sequence of distinct vertices $u = x_0, x_1, \ldots, x_k = v$ such that there exists an edge between vertices $x_{i-1}$ and $x_i$ for all $1 \le i \le k$. 32 33 Input 34 35 The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of each test case follows. 36 37 Each test case begins with an integer $n$ ($3 \le n \le 2\cdot 10^5$) — the number of vertices. 38 39 The second line contains $n$ integers $a_1,a_2,\dots,a_n$ ($1 \le a_i \le 10^6$) — the integer values written on the vertices. 40 41 Each of the next $n-1$ lines contains two integers $u,v$ ($1 \le u,v \le n$), denoting an edge of the tree. It is guaranteed that the edges form a tree. 42 43 It is guaranteed that the sum of $n$ over all the test cases does not exceed $2\cdot 10^5$. 44 45 Output 46 47 For each test case output the number of good triplets in the tree. 48 49 Example 50 51 Input 52 53 ``` 54 4 55 56 5 57 58 1 1 1 1 1 59 60 1 2 61 62 2 3 63 64 2 4 65 66 4 5 67 68 10 69 70 1 2 3 4 5 6 7 8 9 10 71 72 1 3 73 74 2 6 75 76 6 7 77 78 5 4 79 80 8 3 81 82 3 4 83 84 4 6 85 86 9 1 87 88 10 2 89 90 6 91 92 12 6 3 18 9 2 93 94 3 4 95 96 4 5 97 98 2 6 99 100 6 1 101 102 4 2 103 104 8 105 106 3 16 9 1 8 16 4 9 107 108 2 1 109 110 3 1 111 112 4 3 113 114 3 5 115 116 6 3 117 118 4 7 119 120 8 1 121 ``` 122 123 Output 124 125 ``` 126 10 127 128 48 129 130 0 131 132 40 133 ``` 134 135 Note 136 137 For the first test case, all the unordered triplets of three distinct vertices are good: 138 139 1. $\{1, 2, 3\}$ 140 2. $\{1, 2, 4\}$ 141 3. $\{1, 2, 5\}$ 142 4. $\{1, 3, 4\}$ 143 5. $\{1, 3, 5\}$ 144 6. $\{1, 4, 5\}$ 145 7. $\{2, 3, 4\}$ 146 8. $\{2, 3, 5\}$ 147 9. $\{2, 4, 5\}$ 148 10. $\{3, 4, 5\}$ 149 150 For the second test case, $\{2, 5, 8\}$ is a good triplet. 