问题理解

有一棵树，每条边可以是“重要的”(1)或“不重要的”(0)。
给定若干祖先-后代点对 $(u,v)$ 的限制条件：$u$ 到 $v$ 的路径上必须至少有一条边是重要的。
问有多少种给边赋值的方案满足所有限制。

核心思路

1. 限制的转化

对于每个点对 $(u,v)$，$u$ 是 $v$ 的祖先。限制：$u$ 到 $v$ 的路径上至少有一条边是1。

设 $dep[x]$ 为 $x$ 的深度（根深度为1）。

对于每个点 $v$，考虑所有以 $v$ 为后代的限制 $(u,v)$。
对每个这样的 $u$，限制意味着：从 $u$ 到 $v$ 的路径上必须有1。

等价地，从 $v$ 向上直到 $u$ 的父边（或 $u$ 本身），这段路径必须有1。

定义 $lim[v]$ 为：$v$ 必须在其深度为 $lim[v]$ 的祖先处有重要的边。
更准确地说，$lim[v]$ 表示：在 $v$ 的祖先中，深度 $\ge lim[v]$ 的位置必须有一条重要的边。

初始化 $lim[v] = 1$（深度1是根，表示无限制）。
对于限制 $(u,v)$，更新 $lim[v] = max(lim[v], dep[u]+1)$。

理解：$dep[u]+1$ 表示 $u$ 的父节点深度。
限制 $(u,v)$ 要求：$v$ 到 $u$ 的路径上有1，这意味着在 $u$ 的儿子到 $v$ 的路径上必须包含1。
如果 $u$ 是 $v$ 的祖先，那么 $v$ 必须在深度 $\ge dep[u]+1$ 的祖先处获得1。

2. DP 状态定义

设 $dp[x][i]$ 表示：在 $x$ 的子树中，从 $x$ 出发向上看，第一个重要的边出现在深度为 $i$ 的祖先处（即 $x$ 到深度 $i$ 的祖先的路径上必须有重要的边）。

如果 $i = dep[1] = 1$，表示不需要重要的边。

转移：

• 对 $x$ 的孩子 $y$，合并 $dp[x]$ 和 $dp[y]$。
• 边 $(x,y)$ 可以是重要的或不重要的。
  • 如果 $(x,y)$ 不重要，则 $y$ 向上看的第一个重要边必须和 $x$ 向上看的相同。
  • 如果 $(x,y)$ 重要，则 $y$ 向上看的第一个重要边就是 $dep[x]$（因为 $x$ 是 $y$ 的父节点）。

合并公式：$dp'[x][i] = dp[x][i] \times (\sum_{j} dp[y][j]) + (\sum_{k} dp[x][k]) \times dp[y][i]$

3. 最终答案

对根节点 $1$，答案为 $\sum_{i=1}^{dep[1]} dp[1][i]$，但 $dep[1]=1$，所以答案是 $dp[1][1]$。

4. 优化

直接 DP 是 $O(n^2)$ 的，不可行。
观察到 $dp[x][i]$ 中，$i$ 的范围是 $[1, dep[x]]$ 或与 $lim[x]$ 相关。

用线段树合并优化：

每个节点 $x$ 维护一棵线段树，存储 $dp[x][i]$ 的值，$i$ 为深度。

合并两棵线段树时，需要同时维护两个前缀和 $sumx, sumy$。

关键合并公式（在叶子节点）：

sumy += dp[y][i]
dp'[x][i] = dp[x][i] * sumy + sumx * dp[y][i]
sumx += dp[x][i]

这可以用线段树合并实现，每个节点维护乘法和加法标记。

5. 特殊处理

在 DP 完成后，对每个节点 $x$，如果 $x$ 不是根，需要处理父边 $(fa,x)$：

• 如果父边不重要，保持 $dp[x][i]$ 不变。
• 如果父边重要，则 $x$ 向上看的第一个重要边深度变为 $dep[fa]$。

所以更新：$dp[x][lim[fa]] += \sum_{i=1}^{dep[x]} dp[x][i]$

代码结构

1. 预处理

   • 读入树，计算深度 $dep$
   • 处理限制，更新 $lim[v]$
   • 从上到下传递限制：$lim[v] = max(lim[v], lim[fa])$

2. DP 计算

   • 对每个节点 $x$，初始化线段树：在 $lim[x]$ 处设 $dp[x][lim[x]] = 1$
   • 递归合并子树线段树
   • 处理父边：加上前缀和到 $lim[fa]$ 处

3. 获取答案

   • 根的线段树中，查询 $[1, dep[1]+1)$ 的和

复杂度分析

• 线段树合并：$O(n \log n)$
• 空间：$O(n \log n)$
• 可处理 $n \le 5\times 10^5$

样例验证

以样例1为例：

n=5
边: 1-2, 2-3, 3-4, 3-5
限制: (1,3), (2,5)

计算 $lim$：

• $lim[3] = max(1, dep[1]+1=2) = 2$
• $lim[5] = max(1, dep[2]+1=3) = 3$ 传递后：
• $lim[4] = 1$
• $lim[2] = 2$（从 $lim[3]$ 传来）

DP 计算后得到答案 10，符合样例。

总结

这道题的核心技巧：

1. 将路径限制转化为每个点对祖先深度的要求
2. 设计 DP 状态 $dp[x][i]$ 表示第一个重要边的深度
3. 用线段树合并优化 DP 转移
4. 在合并时维护前缀和，实现 $dp[x][i] \times sum_y + sum_x \times dp[y][i]$ 的转移