Sol
0
部署方案合法的条件是：存在一个点$u$，使得所有搜救范围都包含$u$且所有在搜救范围中出现过的点到$u$的距离不超过$L$。此时我们称部署方案可以被点$u$识别。
定义一种部署方案可以被一条边识别，当且仅当这条边的两个端点都能识别它。
显然，对于某种部署方案，可以识别它的$u$会构成一个连通块，而连通块点数 - 边数 = 1。所以，（每个点可以识别的部署方案数 - 每条边可以识别的部署方案数）就是答案。
设$s_u$表示包含$u$且所有点到$u$的距离均不超过$L$的连通块数，设$s_{(x,y)}$表示既包含在$s_x$里又包含在$s_y$里的连通块数，则
1
用$dp$计算$s_u,s_{(x,y)}$。
设$f_{u,j}$表示只包含$u$子树内的点，且所有点到$u$的距离不超过$j$，且包含了$u$的连通块数。设$g_{u,j}$表示包含了$u$的父亲$fa_u$，且不包含$u$的子树内的点，且所有点到$fa_u$的距离不超过$j$的连通块数。距离定义为两个点之间最短路上的边数。
则
2
用长链剖分优化dp。
设$len_u$表示$u$的子树中深度最深的点到$u$的距离。观察可知$f_{u,len_u} = f_{u,len_u+1} = f_{u,len_u+2} \cdots$，所以我们只需要算$f_{u,0},f_{u,1},\cdots f_{u,len_u}$就可以了。
处理某个点的$f$的时候，直接让它继承重儿子的信息（这一步要求支持全局+1的操作）。合并轻儿子$v$的时候，对于$f_{v,0},f_{v,1}\cdots f_{v,len_v}$可以直接暴力，剩下的相当于是令$f_u$数组的一个后缀乘上$f_{v,len_v}$。
如果$f_{v,len_v}$不为$0$的话，我们可以让$f_{u,0},f_{u,1} \cdots f_{u,len_v}$都乘上$f_{v,len_v}$的逆元（注意，不应是直接对数组中的数进行乘$f_{v,len_v}$的逆元的操作，而应该将数组中的值赋为“经过当前的全局标记的运算之后为$f_{u,i}\over f_{v,len_v}$”的值），然后打上全局乘以$f_{v,len_v}$的标记。
如果$f_{v,len_v}$为$0$，就相当于是让一段后缀都变成了$0$，我们可以另外维护一个标记$(l,x)$，表示从$l$开始的位置，数组中的值都是$x$（同理，$x$不一定是$0$，而是“经过当前的全局标记的运算之后为$0$”的值）。
$g$的维护则要更加麻烦一些。首先，我们将所有的链分成两类：长度小于$L-1$的，我们只需要记录链顶元素$u$的$g_{u,L-1-len_u},g_{u,L-1-len_u+1} \cdots g_{u,L-1}$就能够算出这个子树内所有点的$g_{v,L-1}$；长度大于等于$L-1$的，记录链顶元素的$u$的$g_{u,0},g_{u,1} \cdots g_{u,L-1}$即可。而从某个点到它的重儿子时，$g_u$的长度至多加$1$。这样状态数降到了$O(n)$。
直接让重儿子继承当前点的$g$（这个也要求支持全局+1），然后把其他儿子的贡献$(f_{v,j}+1)$合并上来（这个需要支持对后缀的乘法，与$f$的处理类似）。而对于轻儿子$v$，把$\prod_{v’\in son_u,v’\neq v}(f_{v’,j}+1)$分为三部分：1.在我们处理这个轻儿子之前遍历过的轻儿子的贡献；2.还没有遍历过的轻儿子的贡献；3.重儿子的贡献。按照$len$从小到大的顺序依次处理轻儿子，就能够及其方便地统计在当前的轻儿子之前遍历过的轻儿子的贡献；在计算$f$的时候，我们按照轻儿子的$len$从大到小的顺序来合并，把$v$被并入之后的我们对$f$的那些操作撤销掉，就可以得到$v$被并入之前的$f$，也就是2. 3.两部分的贡献。
3
将儿子按照$len$排序，可以先把重儿子找出来，然后对剩下的进行基数排序。这样总复杂度为$O(n)$。
实际上我们需要用到的逆元只有每个点的$f_{u,len_u}$，可以在$O(n)$的时间预处理出它们的逆元。
总复杂度$O(n)$。