【点分治 | 容斥】P15947 [JOI Final 2026] 集邮 5 / Collecting Stamps 5

树上点对问题显然想到点分治，处理出点 $i$ 到当前重心的距离 $d_i$，则点对 $(i,j)$ 能成为答案需满足：

• $d_i+d_j\le D$；
• $\mathrm{\exists }x\in \mathrm{path}(\mathrm{rt},i),d_i-d_x\ge T_x$，即 $d_i\ge T_x+d_x$；
• $\mathrm{\exists }x\in \mathrm{path}(\mathrm{rt},j),d_i+d_x\ge T_x$，即 $d_i\ge T_x-d_x$。

对于第二、第三个条件，存在不好做，贪心可以转换为 $d_i\ge \underset{x\in \mathrm{path}}{min}\{T_x+d_x\}$，在 getdis 记录一下即可解决二。然而“二或三”还是不好做，而一是简单点分治问题，因此可以用满足一的点减去二和三都不满足的点，于是就变成一和三的数点问题，使用树状数组二维偏序解决，时间复杂度 $O(n{\log }^{2}n)$。