拒绝「命运」的安排。

小清新题。

这题给我最大的启示就是：不要被经验限制，开放思维，尝试不同的角度，一些平平无奇的性质可能就是解题的关键。

首先注意到，题目中的限制很可以容斥的样子。但事实上，如果一直将思维卡在容斥，这题就真的做不出来了。

我的思路比较清奇，我一开始想到的是 dp，将限制条件存入 $u$ 节点的 std::vector，然后一遍 dfs 算出来。

然而这样想同样存在一个问题，就是 $v$ 的分布不好处理。你会发现在这种思路中，我们几乎没办法确定方案。

归根结底是这样的 dp 过程能利用的有效信息太少，状态不好设计和转移。考虑正难则反。

不难发现，对于两组限制 $(u_1,v)$ 和 $(u_2,v)$，不妨设 $\mathrm{dep}(u_1)\le \mathrm{dep}(u_2)$，此时只用考虑 $u_2$ 的限制。

通过这个小思考，我们发现可以将此时还未处理到的最深的上节点的深度存入状态，进行转移。

令 $f(u,i)$ 表示处理了 $u$ 的子树，此时最深的未满足的限制的上节点深度为 $i$ 的方案数。

考虑加入一个子树，枚举 $u\to v$ 这条树边的权值：

权值为 1：则 $v$ 以上的限制全部被满足，最大深度仍由 $u$ 的子树提供，即 $f(u,i)\gets f(u,i)\times \sum\limits_{k=0}^{\mathrm{dep}(u)} f(v,k)$。

权值为 0：此时 $i$ 有可能是由 $u$ 的子树取到，也可能是由 $v$ 的子树取到，故 $f(u,i)\gets f(u,i)\times \sum\limits_{k=0}^{i}f(v,k)+f(v,i)\times \sum\limits_{k=0}^{i-1} f(u,k)$。

其中第二个和式上边界 -1 的原因是 $f(u,i)\times f(v,i)$ 已经在第一个和式中计算过，避免重复。

综上，$f(u,i)\gets f(u,i)\times \sum\limits_{k=0}^{\mathrm{dep}(u)} f(v,k)+f(u,i)\times \sum\limits_{k=0}^{i}f(v,k)+f(v,i)\times \sum\limits_{k=0}^{i-1} f(u,k)$。

直接 dp 可以获得 64pts，发现有效节点不多，把虚树建出来就可以获得 72pts，但我并不会建虚树。

（当然这题数据水，一部分出题人想不到的 $\mathcal O(n^2)$ 解法没被卡，甚至铃酱的 $\mathcal O(n^2\log n)$ 做法被放过去了，这很 CCF）

注意到这个 dp 的状态和深度有关，而且涉及求和，这正是线段树合并擅长的。

综上，使用线段树合并进一步优化 dp，时间复杂度 $\mathcal O(n\log \mathrm{dep})$，其中 $\rm dep$ 为深度最大的节点深度。