XSY1602

题意

给定(n)点树，给定(l_i,r_i)，要求给每个点(a_i)，(s.t. l_ile a_ile r_i)，使得相邻点对((u,v))，(s.t.(a_u,a_v)=1)。求所有方案节点(i)的(a_i)和。（(nle 50,1le l_ile r_ile 50000)）

做法

钦定(1)为根
令(f_{i,j})为(i)子树全部的(a)确定完了，(a_i=j)的方案数
(g_{v,i}=mu(i)sumlimits_{j|i}f_{v,j})，则(f_{x,i}=prod(sumlimits_{j|i}g_{v,j}))

然后换下根就行了，(O(nVlogV))