题解 | NC610路径积

题意分析

这道题没有故事背景，直接给出了数学模型，一棵个节点的无根树（个节点，条边的无环连通图），每个节点有一个权值。

询问比较特殊，一共有次查询，每一次是让求从点到点的最短路径上的所有点权的乘积（对取模）。

其实很多人看到最短路径就准备直接Floyd算法、Dijkstra算法、SPFA算法了，但是慢！！把板子都先收起来哈，我们慢慢分析一下，这道题只有点权都没有边权怎么搞最短路？而且这是棵树任意两点之间只有唯一的路径啊！

所以这道题其实就是让我们求树上的路径，然后再把路径上的点权乘积就可以了。

暴力做法

先来说一个暴力做法吧，可以直接在图上做深度优先搜索，不过可以采用邻接表（链式前向星）进行图的存储，需要定义如下内容：

struct Line { //定义边的类型
    int to, next; //to表示这条边指向的点，next表示同一个起点的下一条边的编号
};
vector<int> lst; //存储每个点最后一条边的编号
vector<Line> line;

加边的操作如下：

void add(int x, int y) {
    Line tmp; //定义当前边
    tmp.to = y; //这条边指向的点为y
    tmp.next = lst[x]; //这条边同起点的下一条边编号即为该起点当前最后一条边的编号
    line.push_back(tmp); //将这一条边存储起来
    lst[x] = line.size() - 1; //更新起点的最后一条边的编号
}

通过具体例子理解一下，：
1.初始化时还没有添加边，注意lst初始化均为：

2.第一条边是点和点之间的，不过需要注意由于是无向图，所以要拆成两条边，分别是从点到点和从点到点：

3.第二条边是点和点之间的：

4.最后一条边是点和点之间的：

这种存储方法的好处是我们可以直接遍历从一个点开始的所有边：

void find(int x) {
    for(int l = lst[x]; l != -1; l = line[l].next) { //l表示当前枚举边的编号，从以x为起点的最后一条边开始，逐步往后找，直到-1
        int z = line[l].to; //z为这条边的终点
        ...
    }
}

比如说我们要枚举所有以点为起点的边：
1.根据lst数组得到最后一条边的编号：

2.这条边遍历完之后再去找下一条边：

3.再去找下一条边，直到没有下一条边：

最后再附一下搜索部分的代码：

void find(int n, int x, int y) {
    if(x == y) { //如果找到了终点
        int l = tmp.size(); //记录从点x到点y的路径长度
        mul = 1; //答案为乘积，初始化为1
        for(int i = 0; i < l; ++i) { //计算路径乘积结果
            mul *= val[tmp[i]];
            mul %= MOD;
        }
        flag = true; //由于是树，路径唯一，找到答案后就可以直接进行标记
        return;
    }
    for(int l = lst[x]; l != -1; l = line[l].next) { //枚举以点x为起点的所有边
        int z = line[l].to; //这条边的终点是点z
        if(!vis[z]) { //如果点z还没有被遍历过
            vis[z] = true; //将这个点进行标记
            tmp.push_back(z); //将这个点放到路径中
            find(n, z, y); //从这个新的点继续进行遍历
            tmp.pop_back(); //回溯
            vis[z] = false;
            if(flag) { //如果找到答案了就可以直接返回了
                return;
            }               
        }
    }
}

这种做法可以通过个测试点。
空间复杂度（邻接表存储边的信息）
时间复杂度（由于是树，所以深搜的话每个点只会被遍历一次）

常规做法

树上找路径直接用LCA（Least Common Ancestors，最近公共祖先）就可以了。题目中说是无根树，那么随便找一个点作为根把树构建出了就可以了，可以用递归的方式建树，注意同时把每个点的深度和父节点都要进行存储，方便后续找两点之间的路径：

    vector<int> dep, fa; //分别存储每个点的深度和父节点编号
    void build_tree(int x) {
        for(int y = lst[x]; y != -1; y = line[y].next) { //枚举以点x为起点的所有边
            int z = line[y].to; //这条边的终点为z
            if(dep[z] == 0) { //如果z还没有被遍历过
                dep[z] = dep[x] + 1; //更新这个点的深度
                fa[z] = x; //那么这个点的父节点就是点x
                build_tree(z); //继续从这个点进行遍历
            }
        }
    }

最后就是答案的计算过程，对于每一次的询问，先把两个点调整到同一个深度，再不断往上移动直到到达同一个点，即得到结果：

        for(int i = 0; i < m; ++i) {
            mul = 1;
            int s = x[i], t = y[i];
            if(dep[s] < dep[t]) { //为了简化计算，保证s的深度是大于等于t的深度
                swap(s, t);
            }
            while(dep[s] > dep[t]) { //先把两个点调整到同一个深度
                mul *= val[s];
                mul %= MOD;
                s = fa[s];
            }
            while(s != t) { //当两个点还不相同，分别向上移动一个深度
                mul *= val[s];
                mul %= MOD;
                s = fa[s];
                mul *= val[t];
                mul %= MOD;
                t = fa[t];
            }
            mul *= val[s]; //不要忘记计算最后相同的这个点
            mul %= MOD;
            ans.push_back(mul);
        }

以下图为例，如果，首先交换，其次将点调整到和点同样的高度，即点，最后将两个点同时进行高度的上升直到成为同一个点，那么点经过点分别为，点经过的点分别为，最后的路径为。

另外一个例子，如果，方法是同样的，得到最后的路径为。

空间复杂度（邻接表存储边的信息）
时间复杂度（其中为树的平均深度，不过最坏的时候会达到，这个只是最暴力的LCA求法，所以复杂度并没有太过优化，有需要可以考虑更优美的算法~）