Build Towers

#include <bits/stdc++.h>

using namespace std;

#define ll     long long
#define _test   int _TEST; cin>>_TEST; while(_TEST--)

#define MOD 1000000007

const int N = 3000005;
ll int fact[N], invfact[N];

ll int pow(ll int a, ll int b, ll int m)
{
    ll int ans=1;
    while(b)
    {
        if(b&1)
            ans=(ans*a)%m;
        b/=2;
        a=(a*a)%m;
    }
    return ans;
}

ll int modinv(ll int k)
{
    return pow(k, MOD-2, MOD);
}

void precompute()
{
    fact[0]=fact[1]=1;
    for(int i=2;i<N;i++)
    {
        fact[i]=fact[i-1]*i;
        fact[i]%=MOD;
    }

    invfact[N-1]=modinv(fact[N-1]);
    for(int i=N-2;i>=0;i--)
    {
        invfact[i]=invfact[i+1]*(i+1);
        invfact[i]%=MOD;
    }
}

ll int nCr(ll int x, ll int y)
{
    if(y>x)
        return 0;
    ll int num=fact[x];
    num*=invfact[y];
    num%=MOD;
    num*=invfact[x-y];
    num%=MOD;
    return num;
}

int main()
{
    precompute();

    _test
    {
        int n;
        cin>>n;

        vector<ll int> a(n);
        for(auto &e: a)     cin>>e;

        vector<vector<int>> tree(n);

        for(int i=0; i<n-1; i++)
        {
            int u, v;
            cin>>u>>v;

            u--, v--;

            tree[u].push_back(v);
            tree[v].push_back(u);
        }

        vector<int> needTower(n, 0);

        function<void(int, int)> DFS = [&](int u, int p)
        {
            for(auto v: tree[u])
            {
                if(v == p)      continue;

                DFS(v, u);

                needTower[u] = max(needTower[u], needTower[v]);
            }

            if(a[u] > 0)        needTower[u] = 1;
        };

        DFS(0, -1);

        vector<ll int> vals(n, 1);
        vector<ll int> tot(n, 0);

        function<void(int, int)> DFS2 = [&](int u, int p)
        {
            tot[u] = a[u];

            for(auto v: tree[u])
            {
                if(v == p)          continue;
                if(!needTower[v])   continue;

                DFS2(v, u);

                (vals[u] *= nCr(tot[u]+tot[v], tot[u])) %= MOD;
                (vals[u] *= vals[v]) %= MOD;
                tot[u] += tot[v];
            }

            tot[u]++;
        };

        DFS2(0, -1);

        cout<<vals[0]<<"\n";
    }
}