题意：

给你一棵 个节点的无根树，每个节点有一个权值，给你 次询问，每次询问你需要求出点 到点 之间的简单路径所经过的点的权值积，答案对 取模。

方法一（暴力求解）

对于每次询问，我们可以把点 和点 都跳到它们的最近公共祖先上，然后把经过的点的权值作为贡献乘到答案里。
接下来是如何跳到最近公共祖先上？
我们可以首先预处理出每个点的深度，每个点的父亲节点，显然只需要一次DFS即可。
然后我们可以把点 和点 暴力往上跳，直到跳到它们的最近公共祖先上。
具体的：每次选择深度较大的一个点往上跳，直到跳到跟另外一个点深度相同。接着两个点同时向上跳，直到两个点相遇，即找到最近公共祖先。把跳的过程中遇到的点的权值乘到答案里即可。
代码：

class Solution {
public:
    const int mod=1e9+7;
    struct graph{
        int head[100005],nxt[100005<<1],to[100005<<1],cnt;
        inline graph():cnt(1){}
        inline void add(int u,int v){
            nxt[++cnt]=head[u];
            to[cnt]=v;
            head[u]=cnt;
        }
        inline void clear(){
            cnt=1;
            memset(head,0,sizeof head);
            memset(nxt,0,sizeof nxt);
            memset(to,0,sizeof to);
        }
    }gr;//链式前向星存图
    int val[100005];//val[i] 表示点i的权值
    int dep[100005];//dep[i] 表示点i的深度
    int father[100005];//father[i] 表示点i的父亲节点
    void dfs(int u){//预处理出dep数组和father数组
        dep[u]=dep[father[u]]+1;//当前节点的深度=父亲节点的深度+1
        for(int i=gr.head[u];i;i=gr.nxt[i]){
            int v=gr.to[i];
            if(v==father[u])continue;
            father[v]=u;
            dfs(v);
        }
    }
    int query(int x,int y){
        if(dep[x]<dep[y])swap(x,y);//每次先选择深度较大的点向上跳
        int res=1;
        while(dep[x]>dep[y]){
            res=1ll*res*val[x]%mod;
            x=father[x];
            if(x==y){//如果x和y的最近公共祖先就是y
                res=1ll*res*val[x]%mod;
                return res;
            }
        }
        //此时x和y的深度一样，两个一起往上跳
        while(x!=y){
            res=1ll*res*val[x]%mod;
            res=1ll*res*val[y]%mod;
            x=father[x];
            y=father[y];
        }
        //此时x=y
        res=1ll*res*val[x]%mod;
        return res;
    }
    inline void clearAll(){
        gr.clear();
        memset(val,0,sizeof val);
        memset(dep,0,sizeof dep);
        memset(father,0,sizeof father);
    }
    vector<int> solve(int n, int m, vector<int>& a, vector<int>& u, vector<int>& v, vector<int>& x, vector<int>& y) {
        clearAll();
        for(int i=1;i<=n;i++){
            val[i]=a[i-1];
        }
        for(int i=1;i<n;i++){//n-1条边
            gr.add(u[i-1],v[i-1]);
            gr.add(v[i-1],u[i-1]);
        }
        dfs(1);
        vector<int> ans;
        for(int i=0;i<m;i++){
            ans.push_back(query(x[i],y[i]));
        }
        return ans;
    }
};

时间复杂度：对于每次询问，最坏情况是要跳n个点，所以时间复杂度是
空间复杂度：所有数组的规模都是 的，故空间复杂度为

方法二（正解）

前置知识：树上倍增

我们可以利用倍增法来优化方法一的跳的过程。
具体的：
我们令 表示点x向上跳 步遇到的点。
我们令 表示包括点x在内的向上 个点的权值积。
那么，如何求解上面两个数组呢？
显然有：


（跳步 相当于先跳 步，再跳 步）
于是我们可以DFS整棵树的过程中求解出上面的数组。
由于任意一个数字我们都可以进行二进制分解，故一个点跳任意步数我们都可以用上面的数组实现。
于是我们就把 的暴力跳优化到 了。
代码：

class Solution {
public:
    const int mod=1e9+7;
    struct graph{
        int head[100005],nxt[100005<<1],to[100005<<1],cnt;
        inline graph():cnt(1){}
        inline void add(int u,int v){
            nxt[++cnt]=head[u];
            to[cnt]=v;
            head[u]=cnt;
        }
        inline void clear(){
            memset(head,0,sizeof head);
            memset(nxt,0,sizeof nxt);
            memset(to,0,sizeof to);
            cnt=1;
        }
    }gr;//链式前向星存图
    int up[100005][18],tval[100005][18],dep[100005];
    //up，tval数组见题解，dep[i]表示点i的深度
    void dfs(int u,int fa){//首先dfs整棵树，预处理出上面的数组
        dep[u]=dep[fa]+1;
        for(int j=1;j<=17;j++){
            up[u][j]=up[up[u][j-1]][j-1];
            tval[u][j]=1ll*tval[u][j-1]*tval[up[u][j-1]][j-1]%mod;
        }
        for(int i=gr.head[u];i;i=gr.nxt[i]){
            int v=gr.to[i];
            if(v==fa)continue;
            up[v][0]=u;
            dfs(v,u);
        }
    }
    int query(int x,int y){
        if(dep[x]<dep[y])swap(x,y);
        int res=1;
        for(int j=17;j>=0;j--){//首先选择深度较大的点往上跳，
            if(dep[up[x][j]]>=dep[y]){
                res=1ll*res*tval[x][j]%mod;
                x=up[x][j];
            }
            if(x==y){//如果x和y的最近公共祖先就是y
                res=1ll*res*tval[x][0]%mod;
                return res;
            }
        }
        for(int j=17;j>=0;j--){
            if(up[x][j]!=up[y][j]){//然后两个点一起跳
                res=1ll*res*tval[x][j]%mod;
                res=1ll*res*tval[y][j]%mod;
                x=up[x][j];
                y=up[y][j];
            }
        }
        /*此处可画图理解*/
        res=1ll*res*tval[x][0]%mod;
        res=1ll*res*tval[y][0]%mod;
        res=1ll*res*tval[up[x][0]][0]%mod;
        return res;
    }
    inline void clearAll(){//多测要清空
        gr.clear();
        memset(up,0,sizeof up);
        memset(tval,0,sizeof tval);
        memset(dep,0,sizeof dep);
    }
    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=0;i<n;i++){
            tval[i+1][0]=a[i];
        }
        for(int i=1;i<n;i++){
            gr.add(u[i-1],v[i-1]);
            gr.add(v[i-1],u[i-1]);
        }
        dfs(1,0);
        vector<int> ans;
        for(int i=0;i<m;i++){
            ans.push_back(query(x[i],y[i]));
        }
        return ans;
    }
};

时间复杂度： 次询问，每次询问都是 的，故时间复杂度为
空间复杂度：我们需要预处理出倍增数组 和 ，都是 规模的，故空间复杂度为