XSY1602

题意

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

做法

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

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

XSY1602

原文：https://www.cnblogs.com/Grice/p/12672300.html