描述

这是一篇面对初级coder的题解。

知识点：

LCA

难度： 四星

题解

题目：

给定一棵$nn$n个节点的无根树($nn$n个结点，$n-1n-1$n−1条边的无环连通图)，每个节点有一个权值$a_{i}a\_i$ai​一共有$mm$m次查询，每次查询$x_{i}x\_i$xi​到$y_{i}y\_i$yi​的最短路径上所有点权的乘积。为了防止答案过大，答案对$1e9+71e9+7$1e9+7取模。

分析：

这是一个最短路径的搜索问题，可以考虑深度优先搜索（DFS）和广度优先搜索（BFS），由于要求使路径最短，且结构是一个无环全联通的结构，广度优先搜索可以确保找到的第一个点就是路径最短点。但是由于本题要求的返回值是路径，在利用广度优先搜索构建时需要维护一个表来记录每个节点的父节点。

方法一：广度优先搜索

第一步：利用哈希的形式构建点与点之间的关系

第二步：采用广度优先搜索进行搜索

第三步：根据广度优先搜索得到的值进行回溯

上图展示了一种典型的广度优先搜索，但是可以看到，这个图是有环的，所以不能用下面提到的LCA算法

同时，广度优先搜索还要维护一个队列，记录搜索过的点

class Solution {
public:
const int mod=1e9+7;//取余常数
map<int,vector<int>> graph;//map 以O(1)时间快速找到相邻点
    void addque(int data,queue<int>& que,vector<int>& before){//广度优先搜索，加入队列
        int size=graph[data].size();
        for(int i=0;i<size;i++){
            if(before[graph[data][i]]==-1){//排除已经加入过的点
                que.push(graph[data][i]);
                before[graph[data][i]]=data;//记录加入点的父节点
                }
        }
    }
    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++){//建立map
            graph[u[i]].push_back(v[i]);
            graph[v[i]].push_back(u[i]);
        }
        vector<int> ans(m,1);//返回值
        for(int i=0;i<m;i++){
            int begin= x[i];
            int end = y[i];
            queue<int> que; //广度优先搜索队列
            vector<int> before(n+1,-1);//上一个点值用于回溯
            before[begin]=-2;//初始化起始点
            que.push(begin);//第一点加入队列
            while(before[end]==-1){
                int data=que.front();
                que.pop();
                addque(data,que,before);//广度优先搜索加入队列
            }
            int data=end;
            long long temp=1;//累乘值
            while(data!=begin){//回溯
                temp=temp*a[data-1]%mod;//累乘
                data=before[data];
            }
            temp=temp*a[begin-1]%mod;
            ans[i]=temp;
        }
        return ans;
    }
};

复杂度分析：

空间复杂度$O\left(n\right)O(n)$O(n) 主要消耗是map存储边的信息，以及记录前向节点的列表。

时间复杂度$O\left(mn\right)O(mn)$O(mn) 对每个节点n进行一次广搜，最坏情况下要遍历n个点

运行测试：

15/18 组用例通过 超时 运行时间 3001ms 占用内存 1412KB

方法二：LCA算法

我们发现，本题的特点在于多次询问，而之前建好的树若重复使用，可以用LCA算法重复利用。

对于输入的这棵树，先对其进行树链剖分处理。显然，树中任意点对(u,v)只存在两种情况：

1. 两点在同一条重链上。
2. 两点不在同一条重链上。

对于1，LCA(u,v) 明显为u,v两点中深度较小的点，即min(deep[u],deep[v])。

对于2，我们只要想办法将u,v两点转移到同一条重链上即可。 所以，我们可以将u,v一直上调，每次将u,v调至重链顶端，直到u,v两点在同一条重链上即可。

class Solution {
public:
const int mod=1e9+7;//取余常数
    vector<int> solve(int n, int m, vector<int>& a, vector<int>& u, vector<int>& v, vector<int>& x, vector<int>& y) {
        map<int,vector<int>> graph;//map 以O(1)时间快速找到相邻点
        for(int i=0;i<n;i++){//建立map
            graph[u[i]].push_back(v[i]);
            graph[v[i]].push_back(u[i]);
        }
        int begin= 1;
        queue<int> que; //广度优先搜索队列
        vector<int> before(n+1,-1);//上一个点值用于回溯
        vector<int> dep(n+1,-1);//深度值用于LCA
        before[begin]=-2;//初始化起始点
        dep[begin]=0;
        que.push(begin);//第一点加入队列
        while(que.size()!=0){
             int data=que.front();
             que.pop();
             //广度优先搜索加入队列
            int size=graph[data].size();
            for(int i=0;i<size;i++){
                if(before[graph[data][i]]==-1){//排除已经加入过的点
                    que.push(graph[data][i]);
                    before[graph[data][i]]=data;//记录加入点的父节点
                    dep[graph[data][i]]=dep[data]+1;//更新加入点的深度
                }
            }
        }
        vector<int> ans(m,1);//返回值
        for(int i=0;i<m;i++){
            int begin= x[i];//开始
            int end = y[i];//结束
            long long temp=1;//累乘值
            if(dep[begin]<dep[end])
                swap(begin,end);
            while(dep[begin]!=dep[end]){//更新到同一深度
                temp=temp*a[begin-1]%mod;//累乘
                begin=before[begin];
            }
            while(begin!=end){//同时向上回溯
                temp=temp*a[begin-1]%mod;//累乘
                temp=temp*a[end-1]%mod;//累乘
                begin=before[begin];
                end=before[end];
            }
            temp=temp*a[end-1]%mod;//公共父祖先只加入一次
            ans[i]=temp;
        }
        return ans;
    }
};

模拟如下

复杂度分析：

空间复杂度$O\left(n\right)O(n)$O(n) 主要消耗是map存储边的信息，以及记录前向节点的列表。

时间复杂度$O\left(mn\right)O(mn)$O(mn) 对每个节点n进行一次广搜，最坏情况下要遍历n个点

运行测试：

通过全部用例 运行时间 154ms 占用内存 17660KB

总结

LCA 算法必须无环才能用