贪心的正确性是显然的，至此思维难度结束。

代码的细节主要在于两个字符串自由区间的交错问题，大概写+调了30min。

注意到 $v\ge 2$，因此对于一个已知的 $\{(a_i,b_i)\}$，最优策略一定是尽可能躲开 $(a,b)$ 的限制。

所以一个 $\{(a_i,b_i)\}$ 不合法，当且仅当存在从 $(c_i,d_i)$ 到 $(c_{i+1},d_{i+1})$ 的链接，且链接过去的值不满足条件。

随便数一数就行。写起来比 A 快。

想的最久的一题。

构造一个图 $G$，点为原树的边，并且每个点对应的边集构成一个完全图，那么问题转化为在图 $G$ 上定根的 dfs 树计数。

一个重要的观察是 dfs 树没有返祖边，因此每一个边集完全图在 dfs 树上一定呈现为一条链，而链与链之间的交点是固定的。至此再把问题转化为，对于每一条链都钦定一个顺序的方案数。

考虑定根的影响。发现定根意味着对于每一个边集完全图，其对应的链的一个端点会由根确定。具体地，若根为 $x$，$x$ 子树内的边集对应的链，其中一端一定为父边；子树外边集对应的链，其中一端一定为走到 $x$ 经过的边。

至此定根就非常好算了，其实就是 $\prod (deg-1)$。对于多定根的情况考虑容斥，即求 $\sum (-1)^{|S|}f(S)$。

进一步观察，$S$ 内的点一定要位于一条简单路径上，否则一定存在一个边集被钦定三个端点；而对于一个简单路径上的关键点，其有效约束点只有简单路径的两个端点。对于该点集 $S$，$f(S)=\prod_{i\in \text{path}}(deg_i-2)\prod_{i\not\in\text{path}}(deg_i-1)$

因此我们设 $f_{x,0/1}$ 表示子树 $x$ 内选择了一条链，链上有奇数/偶数个关键点的方案数的 $\sum (\prod\frac{deg-2}{deg-1})$，转移是简单的。

时间复杂度 $O(n)$。

NOIP D<C 是什么神秘仪式吗。

不会那个神秘结论，想的时候走了挺多弯路，但传统DS切入点非常有限，还是做得出来。

考虑枚举 $lca$ 处的点 $x$，那么 $x$ 的贡献是若干个在子树节点未出现的极长编号连续段。

注意到这个极长编号连续段的个数是 $O(n)$ 的，因为段与段无交，可以看作对 $n$ 个点建树，总段数 $\le 2n-1$。

一个段 $[L,R]$ 对一组询问有贡献，当且仅当 $\max(L,ql)+qk-1\le \min(R,qr)$。

注意到 $ql+qk-1\le qr$ 是恒成立的，因此上式是一个三维偏序，cdq分治即可。

时间复杂度 $O(n\log^2n)$。