#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
 
int main(){
 
    int tt = 1;
    cin >> tt;
 
    while(tt--){
        ll n;
        cin >> n;
 
        vector<ll> a(n);
        for(ll i = 0; i < n; i++) cin >> a[i];
 
        vector<vector<ll>> v(n);
        for(ll i = 1; i < n; i++){
            ll x, y;
            cin >> x >> y;
            x--;
            y--;
            v[x].push_back(y);
            v[y].push_back(x);
        }
 
        ll ans = 0;
        vector<ll> ss(n, 1);
 
        function<void(ll, ll)> dfs = [&](ll u, ll par){
 
            vector<ll> val;
            for(auto& z : v[u]) if(z != par){
                dfs(z, u);
                val.push_back(ss[z]);
                ss[u] += ss[z];
            }
 
            val.push_back(n - ss[u]);
            assert(accumulate(val.begin(), val.end(), 0ll) == n - 1);
 
            if((ll)sqrtl(a[u]) * (ll)sqrtl(a[u]) < a[u]) return;
 
            ll sum = 0;
            ll pairs = 0;
            ll triplets = 0;
 
            for(auto& z : val){
                triplets += pairs * z;
                pairs += sum * z;
                sum += z;
            }
 
            ans += pairs;
            ans += triplets;
        };
 
        dfs(0, -1);
 
        cout << ans << '\n';
    }
 
    return 0;
}

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKIAojZGVmaW5lIGxsIGxvbmcgbG9uZwogCmludCBtYWluKCl7CiAKICAgIGludCB0dCA9IDE7CiAgICBjaW4gPj4gdHQ7CiAKICAgIHdoaWxlKHR0LS0pewogICAgICAgIGxsIG47CiAgICAgICAgY2luID4+IG47CiAKICAgICAgICB2ZWN0b3I8bGw+IGEobik7CiAgICAgICAgZm9yKGxsIGkgPSAwOyBpIDwgbjsgaSsrKSBjaW4gPj4gYVtpXTsKIAogICAgICAgIHZlY3Rvcjx2ZWN0b3I8bGw+PiB2KG4pOwogICAgICAgIGZvcihsbCBpID0gMTsgaSA8IG47IGkrKyl7CiAgICAgICAgICAgIGxsIHgsIHk7CiAgICAgICAgICAgIGNpbiA+PiB4ID4+IHk7CiAgICAgICAgICAgIHgtLTsKICAgICAgICAgICAgeS0tOwogICAgICAgICAgICB2W3hdLnB1c2hfYmFjayh5KTsKICAgICAgICAgICAgdlt5XS5wdXNoX2JhY2soeCk7CiAgICAgICAgfQogCiAgICAgICAgbGwgYW5zID0gMDsKICAgICAgICB2ZWN0b3I8bGw+IHNzKG4sIDEpOwogCiAgICAgICAgZnVuY3Rpb248dm9pZChsbCwgbGwpPiBkZnMgPSBbJl0obGwgdSwgbGwgcGFyKXsKIAogICAgICAgICAgICB2ZWN0b3I8bGw+IHZhbDsKICAgICAgICAgICAgZm9yKGF1dG8mIHogOiB2W3VdKSBpZih6ICE9IHBhcil7CiAgICAgICAgICAgICAgICBkZnMoeiwgdSk7CiAgICAgICAgICAgICAgICB2YWwucHVzaF9iYWNrKHNzW3pdKTsKICAgICAgICAgICAgICAgIHNzW3VdICs9IHNzW3pdOwogICAgICAgICAgICB9CiAKICAgICAgICAgICAgdmFsLnB1c2hfYmFjayhuIC0gc3NbdV0pOwogICAgICAgICAgICBhc3NlcnQoYWNjdW11bGF0ZSh2YWwuYmVnaW4oKSwgdmFsLmVuZCgpLCAwbGwpID09IG4gLSAxKTsKIAogICAgICAgICAgICBpZigobGwpc3FydGwoYVt1XSkgKiAobGwpc3FydGwoYVt1XSkgPCBhW3VdKSByZXR1cm47CiAKICAgICAgICAgICAgbGwgc3VtID0gMDsKICAgICAgICAgICAgbGwgcGFpcnMgPSAwOwogICAgICAgICAgICBsbCB0cmlwbGV0cyA9IDA7CgogICAgICAgICAgICBmb3IoYXV0byYgeiA6IHZhbCl7CiAgICAgICAgICAgICAgICB0cmlwbGV0cyArPSBwYWlycyAqIHo7CiAgICAgICAgICAgICAgICBwYWlycyArPSBzdW0gKiB6OwogICAgICAgICAgICAgICAgc3VtICs9IHo7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIGFucyArPSBwYWlyczsKICAgICAgICAgICAgYW5zICs9IHRyaXBsZXRzOwogICAgICAgIH07CiAKICAgICAgICBkZnMoMCwgLTEpOwogCiAgICAgICAgY291dCA8PCBhbnMgPDwgJ1xuJzsKICAgIH0KIAogICAgcmV0dXJuIDA7Cn0=

NAo1CjEgMSAxIDEgMQoxIDIKMiAzCjIgNAo0IDUKMTAKMSAyIDMgNCA1IDYgNyA4IDkgMTAKMSAzCjIgNgo2IDcKNSA0CjggMwozIDQKNCA2CjkgMQoxMCAyCjYKMTIgNiAzIDE4IDkgMgozIDQKNCA1CjIgNgo2IDEKNCAyCjgKMyAxNiA5IDEgOCAxNiA0IDkKMiAxCjMgMQo0IDMKMyA1CjYgMwo0IDcKOCAxCg==

4
5
1 1 1 1 1
1 2
2 3
2 4
4 5
10
1 2 3 4 5 6 7 8 9 10
1 3
2 6
6 7
5 4
8 3
3 4
4 6
9 1
10 2
6
12 6 3 18 9 2
3 4
4 5
2 6
6 1
4 2
8
3 16 9 1 8 16 4 9
2 1
3 1
4 3
3 5
6 3
4 7
8 1