codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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. ![](https://espresso.codeforces.com/f8e9eef3aadcc6c2c9f0b90e3ffdb4e73776db69.png)