题解

问题分析

题目要求计算以树中每个节点为根的子树中，所有可能的叶子二元组((c,d))对应的纳什均衡点总数的和（对(p)取模）。树的每个非叶节点有且仅有2个儿子，节点按深度分为A类（偶数深度非叶）、B类（奇数深度非叶）和叶节点，A和B分别控制各自节点的重边选择，纳什均衡点需满足双方策略均为最优响应。

核心思路

1. 纳什均衡条件建模：
   对任意策略((f,g))，若为纳什均衡点，则：

   • A固定策略(f)时，B的策略(g)是最优的（无法通过改变策略提高得分）。
   • B固定策略(g)时，A的策略(f)是最优的（无法通过改变策略提高得分）。

   对所有((c,d))求和时，需统计满足上述条件的策略总数，利用树形结构递归计算。

2. 树形DP设计：
   定义(dp[u][c][a])表示以节点(u)为根的子树中，类型为(c)（0对应A类，1对应B类）的节点在得分约束为(a)时的贡献。通过子树合并计算父节点的DP值，利用多项式表示得分约束下的计数关系。

3. 多项式插值优化：
   由于(k)可能很大（(\leq 10^9)），直接计算多项式在(k)处的值效率低下。通过拉格朗日插值或中国剩余定理（CRT），将多项式在模(p)下的计算转化为插值问题，高效求解大参数下的结果。

4. 子树独立计算：
   对每个节点(u)，以其为根重新计算子树的DP值，利用模运算确保结果在(p)下正确，最终输出所有子树的答案。

详细步骤

1. 树结构与节点分类：
   根据父节点列表构建树，计算每个节点的深度，区分A类（偶数深度非叶）、B类（奇数深度非叶）和叶节点。

2. 动态规划初始化：

   • 叶节点：贡献与(c,d)的选择直接相关，初始化(dp)值为1（基础计数单位）。
   • 非叶节点：根据类型（A/B）合并左右子树的DP值。A类节点需考虑最大化A的得分，B类节点需考虑最大化B的得分，合并时需满足最优响应条件。

3. 多项式表示与插值：
   DP值以多项式形式存储（次数由子树深度决定），通过插值计算多项式在(k)处的值。利用中国剩余定理处理模(p)下的插值，支持大(k)的高效计算。

4. 子树答案合并：
   对每个节点(u)，递归计算其子树的DP值，结合插值结果得到(Ans_u)，输出模(p)后的结果。

代码解析

• 树结构构建：通过父节点列表构建邻接表，计算节点深度。
• DP初始化与合并：叶节点直接初始化，非叶节点根据类型合并左右子树的DP值，处理最优响应条件。
• 多项式插值：利用interpolate命名空间中的工具，通过CRT和多项式插值计算大(k)下的多项式值。
• 模运算处理：使用ModInt类封装模运算，确保所有计算在模(p)下进行，避免溢出。

复杂度分析

• 时间复杂度：(O(n^3))。每个节点的DP计算涉及多项式操作（次数(O(n))），子树遍历为(O(n))，总复杂度为三次方，适合(n \leq 5000)。
• 空间复杂度：(O(n^2))，用于存储树形结构、DP数组及多项式系数。

该方案通过树形DP结合多项式插值，高效处理大参数问题，准确计算每个子树的纳什均衡点总数和，满足题目约束。