#PQJ2294x13454. QOJ 2294_13454

    ID: 2789 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2021 集训动态规划

QOJ 2294_13454

标题: Game on Tree - Problem - QOJ.ac

#13454. Game on Tree

Statistics

The problem was used in the following contests:

Aruba 和 Ball 又在玩游戏,下面将他们分别简称为 A 和 B。

给定一棵 n 个点的有根树,标号从 1 到 n,根的标号是 1。每个节点的儿子数只能为 0 或 2。将节点分成下列三类:

  • A:到根距离为偶数的所有非叶节点的集合,其中根到自己的距离为 0
  • B:到根距离为奇数的所有非叶节点的集合
  • L:叶节点的集合

而对于所有叶子节点 u∈L,都会被分配一个二元组 (c(u),d(u))。其中 c 和 d 可以看成是定义域为 L 的函数。

游戏开始前:

  • A 对于 A 中的每个点 u,从 u 的两条指向儿子的边中选择一条,将其标记为重边;
  • B 对于 B 中的每个点 u,从 u 的两条指向儿子的边中选择一条,将其标记为重边。
  • A 的选择可以看成一个定义域为 A 的映射函数 f;
  • B 的选择可以看成一个定义域为 B 的映射函数 g。

那么一个有序对 (f,g) 被称为一组策略。可以看出,A 有 2|A| 种不同的选择,B 有 2|B| 种不同的选择。所以一共有 2|A|+|B| 组不同的策略。

当策略确定之后,从树根开始,不断沿着重边往下走,直到走到某个叶子节点 u。这时 A 的分数是 c(u),B的分数是 d(u)。一组策略 (f,g) 如果满足以下条件,那么该组策略是一个纳什均衡点:

  • 在 A 的策略不改变的情况下,B 无法通过改变自己的策略获得更高分。即在策略 (f,g′) 中 B 的得分总小于等于 (f,g) 中 B 的得分。
  • 在 B 的策略不改变的情况下,A 无法通过改变自己的策略获得更高分。即在策略 (f′,g) 中 A 的得分总小于等于 (f,g) 中 A 的得分。

给定树形态和 k。令 c 和 d 的值域是 Z∩[1,k],那么一共有 k2|L| 组不同的 (c,d)。
现在要求对每组不同的 (c,d) 都计算纳什均衡点的个数。由于 k2|L| 过大,所以输出这 k2|L| 个答案的和。这个和可能还是过大,所以输出和对 p 取模后的值。即,求

(∑c∈L→[k]∑d∈L→[k]F(c,d))modp

其中 L→[k] 是所有定义域为 L,值域为 [k]={1,2,…,k} 的函数集。 F(c,d) 是指给定 c 和 d 情况下的纳什均衡点个数。


A 和 B 认为这棵树太大了,想要只保留这棵树的一个子树。具体地,对于每一个节点 s,删除树的其他部分,只保留点 s 的子树,并以点 s 作为树根开始游戏,将上面问题的答案记为 Anss。

你需要求出所有 Anssmodp。

输入格式

第一行三个整数 n,k,p(3≤n≤5000,k≤109,n<p≤106)。保证 n 为奇数。

第二行包括 n−1 个整数 fa2,fa3,…,fan。fai 表示 i 的父亲,1≤fai<i。

输出格式

输出 n 行,每行一个数,第 i 行输出 Ansimodp。

样例数据

样例 1 输入

3 2 114514
1 1

样例 1 输出

24
4
4

样例 2 输入

9 2 191981
1 1 3 4 4 3 7 7

样例 2 输出

8960
4
1152
24
4
4
24
4
4

样例 3 输入

11 45 233
1 1 3 3 5 5 4 4 9 9

样例 3 输出

80
161
177
150
80
161
161
161
80
161
161

子任务

  • Subtask 1(20pts):n=99,k≤100,p 是质数。
  • Subtask 2(30pts):n=99。
  • Subtask 3(50pts):n=4999。