令 $D$ 是集合中的点的距离矩阵，则询问的结果相当于 $\operatorname{tr}(D^k)$。我们可以利用这些结果计算出 $\det D$。

具体地，令 $\lambda_1,\ldots,\lambda_n$ 是 $D$ 的所有特征值（记重数），则 $\operatorname{tr}(D^k)=\sum_{i=1}^n\lambda_i^k=p_k$。而 $\det D=\prod_{i=1}^n \lambda _i$。令 $e_k$ 表示 $\lambda_1,\ldots,\lambda_n$ 的第 $k$ 个基本对称多项式，即任选其中 $k$ 个的乘积之和。

由牛顿恒等式可以得到 $$ ke_k=\sum_{i=1}^k(-1)^{i-1}e_{k-i}p_i $$ 从而可以 $O(n^2)$ 递推得到 $e_n=\det D$。

Graham-Pollak 引理：一棵树的距离矩阵的行列式等于 $(-1)^{n-1}2^{n-2}(n-1)$。

证明可以考虑每次用一个叶子和其父亲做消元。在题解给出的论文中，还提供了一系列的拓展公式，利用这些公式我们可以证明删除一个度数为 $d$ 的点后的距离矩阵的行列式等于 $(-1)^{n-2}2^{n-3}((n+3-d)d-4)$。当 $P$ 足够大时，$d=1$ 的值在模 $P$ 意义下和 $d>1$ 的结果都不一样，所以我们可以通过询问 $|V|\setminus \{v\}$ 来判断 $v$ 是否是叶子。