题解：Tree Infection 解题思路与代码解析

问题核心分析

本题要求对有根树中每个顶点 ( s )，计算当 ( s ) 及其距离不超过 ( R ) 的后代被感染时，满足以下条件的顶点对 ((u, v)) 数量：

1. ( u ) 和 ( v ) 均未被感染；
2. ( u ) 和 ( v ) 之间的路径上被感染的顶点数不超过 ( M )；
3. ( 1 \leq u < v \leq N )。

核心思路

通过深度优先搜索（DFS）预处理树的结构特征，结合动态规划统计关键数据，高效计算每个顶点作为感染源时的可达顶点对数量。具体分为以下步骤：

1. 树结构编码：将顶点编号从 ( 0 ) 开始（便于数组处理），用邻接表存储树的边关系。
2. 关键参数定义：
   • ( L = \lfloor \frac{M + 1}{2} \rfloor )：路径感染顶点数限制的一半相关参数；
   • ( K = \max(0, R - L) )：感染范围与路径限制的差值参数。
3. 动态规划数组设计：
   • ( ans0[x] )：以 ( x ) 为根的子树中未被感染的顶点数；
   • ( ans1[x] )：与 ( x ) 距离相关的子树顶点统计；
   • ( ans2[x] )：感染范围内的顶点统计；
   • ( ans3[x] )：最终结果，即顶点 ( x ) 作为感染源时的可达顶点对数量。

代码实现解析

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const ll N = 500005;  // 最大顶点数，适配 5×10^5 规模
vector<ll> v[N];      // 邻接表存储树
ll path[N];           // 记录当前 DFS 路径
ll ans0[N], ans1[N], ans2[N], ans3[N];  // 动态规划数组
ll sz, n, R, M, L, K;  // sz 为当前路径长度，L、K 为关键参数

void dfs(ll x) {
    ans0[x] = 1;  // 初始化为 1（自身为未感染顶点）

    // 遍历子节点（排除父节点，避免回退）
    for (ll y : v[x]) {
        if (!x || y != path[sz - 1]) {
            path[++sz] = y;  // 记录路径
            dfs(y);          // 递归处理子树
            sz--;            // 回溯
        }
    }

    // 更新父节点的 ans0（累计子树未感染顶点数）
    if (1 <= sz) {
        ans0[path[sz - 1]] += ans0[x];
    }

    // 根据 L 计算 ans1（与路径深度相关的统计）
    if (L <= sz) {
        ans1[path[sz - L]] += ans0[x];
    }

    // 根据 R 计算 ans2（感染范围内的顶点统计）
    if (R <= sz) {
        ans2[path[sz - R]] += ans0[x];
    }

    // 计算 ans3 的部分贡献（基于 ans1 的组合数）
    if (K <= sz) {
        ans3[path[sz - K]] += ans1[x] * (ans1[x] - 1) / 2;
    }

    // 结合 M 和 R 的关系，累加跨子树的可达对
    if (R <= M) {
        ans3[x] += (n - ans0[x]) * ans2[x];
    }

    // 累加未感染顶点内部的可达对（总对减去不可达对）
    ans3[x] += (n - ans0[x]) * (n - ans0[x] - 1) / 2;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> R >> M;
    R++;  // 调整 R 为 1-based 计数
    L = (M + 1) >> 1;  // 等价于 floor((M+1)/2)
    K = max(0ll, R - L);

    // 读取父节点信息，构建邻接表（0-based 编号）
    for (ll i = 1; i < n; ++i) {
        ll x;
        cin >> x;
        x--;  // 转换为 0-based
        v[x].push_back(i);
    }

    dfs(0);  // 从根节点（0-based 的 0，对应原题 1）开始 DFS

    // 输出每个顶点作为感染源时的结果
    for (ll i = 0; i < n; ++i) {
        cout << ans3[i] << '\n';
    }

    return 0;
}

关键逻辑说明

1. 树的遍历与路径记录：通过 DFS 遍历树，path 数组记录当前从根到节点的路径，便于计算祖先-后代关系和距离。
2. 动态规划数组更新：
   • ans0[x] 累计以 ( x ) 为根的子树中未被感染的顶点数，用于后续组合数计算；
   • ans1[x] 和 ans2[x] 分别基于参数 ( L ) 和 ( R ) 统计特定范围内的顶点数量，辅助判断路径感染顶点数是否符合条件；
   • ans3[x] 综合上述统计结果，通过组合数公式（如 ( \binom{k}{2} = \frac{k(k-1)}{2} )）计算可达顶点对数量。
3. 复杂度优化：DFS 遍历复杂度为 ( O(N) )，每个节点的处理为常数时间，整体复杂度为 ( O(N) )，可适配 ( N \leq 5 \times 10^5 ) 的数据规模。

总结

该解法通过预处理树结构和动态规划统计，高效计算每个顶点作为感染源时的可达顶点对数量，核心是利用树的递归特性和组合数学简化计数过程，确保在大规模数据下的性能。