C题 路径积

C题 路径积

有个比较笨的方法

1. 以1为根节点dfs整棵树，把每个节点的深度记录下来（deep[]）,并记录每个节点的父节点（pre[]）
2. 然后，对于(x,y),依据deep[]和pre[],可以向上找到x,y第一个公共的父节点root。路径积就是x->root->y，再向上找公共父节点的过程中累乘经过的节点即可。

具体的做法是，取x,y中深度较大的向上查找，类似于x=pre[x]或y=pre[y]这样的形式。

时间复杂度大概在o(n+m*k) ，其中k为树的平均深度（大概是logn QaQ）

上代码：

import java.util.*;


public class Solution {
    /**
     * 路径积
     * @param n int整型
     * @param m int整型
     * @param a int整型一维数组
     * @param u int整型一维数组
     * @param v int整型一维数组
     * @param x int整型一维数组
     * @param y int整型一维数组
     * @return int整型一维数组
     */
    int mod=(int)(1e9+7);
    ArrayList<Integer> map[];
    int[] deep;
    int[] pre;
    void dfs(int node,int last){
        deep[node]=deep[last]+1;
        pre[node]=last;
        for(int next: map[node]){
            if(next==last)continue;
            dfs(next,node);
        }
    }
    int getnum(int[] a,int x,int y){
        long ans=a[x-1]*a[y-1]%mod;
        int last=1;
        while(x!=y){
            ans=ans*last%mod;
            if(deep[x]>deep[y]){
                x=pre[x];last=a[x-1];
            }else {
                y=pre[y];last=a[y-1];
            }
        }
        return (int)ans;
    }
    public int[] solve (int n, int m, int[] a, int[] u, int[] v, int[] x, int[] y) {
        // write code here
        map=new ArrayList[n+1];
        for(int i=0;i<=n;i++)map[i]=new ArrayList<>();
        deep=new int[n+1];
        pre=new int[n+1];
        deep[1]=-1;
        for(int i=0;i<n-1;i++){
            map[u[i]].add(v[i]);
            map[v[i]].add(u[i]);
        }
        dfs(1,1);
        int[] res=new int[m];
        for(int i=0;i<m;i++){
            res[i]=getnum(a,x[i],y[i]);
        }
        return res;
    }
}