路径积

最优解

要求树上路径的点权乘积和，有点麻烦，不妨先定一个根之后求出从根节点到各个点的路径乘积和。
然后对于u->v的路径，假设他们的最近公共祖先为p，那么路径为u->...->p->...->v。只要求出u->p的乘积和，p->v的乘积和即可。这样就转换成了一个前缀乘积除以另一个前缀乘积的形式，利用逆元进行除法运算。
这里使用倍增数组求最近公共祖先，复杂度，总的时间复杂度
空间复杂度，如果使用其他算法求lca，如树链剖分或tarjan算法，空间复杂度可达

#define ll long long
int mod = 1e9 + 7;
int qm(int a, int b){int res = 1;while(b){if(b&1) res = (ll)res*a%mod;a = (ll)a*a%mod; b>>=1;}return res;}
vector<int> g[100005];
int sum[100005], dep[100005];
int f[100005][20];
void dfs(int u, int fa){
    dep[u] = dep[fa] + 1; f[u][0] = fa; sum[u] = (ll)sum[fa]*sum[u]%mod;
    for(int i = 1; i < 20; ++i) f[u][i] = f[f[u][i-1]][i-1];
    for(int v: g[u]) if(v != fa) dfs(v, u);
}
int lca(int u, int v){
    if(dep[v] < dep[u]) swap(u, v);
    int d = dep[v] - dep[u];
    for(int i = 19; i >= 0; --i) if(d>>i&1) v = f[v][i];
    if(u == v) return u;
    for(int i = 19; i >= 0; --i) if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
    return f[u][0];
}
vector<int> solve(int n, int m, vector<int> &a, vector<int> &u, vector<int>&v, vector<int> &x, vector<int> &y){
    for(int i = 1; i <= n; ++i)
        g[i].clear(), sum[i] = a[i-1];
    assert(u.size() == n-1 && v.size() == n-1 && x.size() == m  && a.size() == n && y.size() == m);
    for(int i = 0; i < n-1; ++i){
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
    sum[0] = 1;
    dfs(1, 0);
    vector<int> ans; ans.clear();
    for(int i = 0; i < m; ++i){
        int u = x[i], v = y[i];
        int p = lca(u, v);
        int inv = qm(sum[p], mod-2);
        int t = (ll)sum[u]*sum[v]%mod*(ll)inv%mod*inv%mod*a[p-1]%mod;
        ans.push_back(t);
    }return ans;
}