题目理解

我们有一棵 $n$ 个节点的有根树（根为 $1$），每个节点 $i$ 有一个权值 $v_i$。

给定一个长度为 $k$ 的数组 $A$，构造一个 $k \times k$ 的矩阵 $B$，其中：

$$B_{i,j} = v_{\mathrm{LCA}(A_i, A_j)}$$

即矩阵的 $(i,j)$ 位置的元素是 $A_i$ 与 $A_j$ 的**最近公共祖先（LCA）**的权值。

要求计算矩阵 $B$ 的行列式，并对 $998244353$ 取模。

---

样例分析

样例 1

输入：

3 2
1 2 3
2 3
1 2
1 3

• 节点 1 权值 $1$，节点 2 权值 $2$，节点 3 权值 $3$
• 树：1 是根，2 和 3 是 1 的孩子
• $A = [2, 3]$

矩阵 $B$：

• $B_{1,1} = v_{\mathrm{LCA}(2,2)} = v_2 = 2$
• $B_{1,2} = v_{\mathrm{LCA}(2,3)} = v_1 = 1$
• $B_{2,1} = v_{\mathrm{LCA}(3,2)} = v_1 = 1$
• $B_{2,2} = v_{\mathrm{LCA}(3,3)} = v_3 = 3$

$$B = \begin{bmatrix} 2 & 1 \\ 1 & 3 \end{bmatrix}$$

行列式 $= 2 \times 3 - 1 \times 1 = 5$。

输出：

5

---

矩阵性质与关键转化

矩阵 $B$ 是对称矩阵，因为 $\mathrm{LCA}(x,y) = \mathrm{LCA}(y,x)$。

更重要的结构是：这个矩阵可以写成若干秩 1 矩阵的和。

考虑每个节点 $u$ 对矩阵的贡献。定义向量 $x_u$ 长度为 $k$：

$$(x_u)_i = \begin{cases} 1 & \text{如果 } u \text{ 是 } A_i \text{ 的祖先} \\ 0 & \text{否则} \end{cases} $$

那么：

$$B = \sum_{u=1}^n v_u \cdot (x_u x_u^T)$$

其中 $x_u x_u^T$ 是外积，得到一个 $k\times k$ 矩阵。

---

行列式的简洁表达式

对于这种 LCA 矩阵，存在一个已知结论：

令 $T$ 为 $A$ 中所有点以及它们两两 LCA 构成的集合（即虚树节点集合）。将 $T$ 中点按 DFS 序排序。

那么：

$$\det(B) = \prod_{u \in T} v_u^{c_u} \pmod{998244353} $$

其中 $c_u$ 是在虚树中以 $u$ 为根的子树中包含的原始 $A$ 中的节点数。

---

算法步骤（无代码）

1. 预处理 LCA
   使用倍增法或树链剖分预处理，支持 $O(\log n)$ 查询任意两点的 LCA。

2. 构建虚树

   • 将 $A$ 中所有点按 DFS 序排序。
   • 将相邻点的 LCA 加入集合 $T$。
   • 去重后，用栈算法建立虚树结构。

3. 计算贡献

   • 在虚树上 DFS，计算每个节点 $u$ 的子树中包含的原始 $A$ 中的节点数 $c_u$。
   • 答案 $= \prod_{u \in T} v_u^{c_u} \bmod 998244353$。

---

复杂度分析

• LCA 预处理：$O(n \log n)$
• 虚树构建：$O(k \log k)$（排序和栈操作）
• 总复杂度：$O(n \log n + k \log k)$，可处理 $n,k \leq 5\times 10^5$ 的数据规模。

---

总结

本题的关键在于发现 LCA 矩阵的行列式可以转化为虚树上节点权值的乘积，其中指数由子树中原始查询点的数量决定。利用虚树技术，我们避免了直接计算 $k^2$ 规模的矩阵，从而在高效时间内求解。