原题传送门:>Here<
我们先考虑只求一个点时怎么做。
设$f_i$为$i$到叶结点的最短距离。
假设我们在处理$root$的答案。可以发现,
当$dis_{root,i}\ge f_i$时,$i$的子树只需要放一个人就可以“封锁”。
可以发现满足这个条件的点构成很多棵子树,而我们的答案就是子树的个数。
现在我们考虑怎么得到子树个数。
设$val_i=2-d_i$,其中$d_i$表示点$i$的度数。
我们可以发现,一棵子树的权值和正好等于$1$。
考虑为什么是这样。
设一棵子树中有$x$个点,那么有$x-1$条在子树内的边。所以贡献即为$2*x-2(x-1)=2$。因为我们求的是“子树”权值和,所以必有一条连出去的边。这样贡献即为$2-1=1$。
所以我们只要对于$dis_{i,j}\ge f_j$,将$ans_i$加上$2-d_j$即可。
这样复杂度是$O(n^2)$的。
考虑点分治。则对于$i$,满足条件的$j$满足$dis_i+dis_j\ge f_j$。
移项一下,得到$dis_i\ge f_j-dis_j$。后面那个东西用树状数组维护一下即可。