rt，本题中有保证每个点度数不超过 20，实际上现有题解复杂度最优的也是 $O(nd\log n+n\log^2 n)$ 。但事实上加一个三度化就可以使复杂度变为 $O(n\log^2 n)$，所有题解都没提及，题解也满了。