#PQJ2294x13454. QOJ 2294_13454
QOJ 2294_13454
标题: Game on Tree - Problem - QOJ.ac
#13454. Game on Tree
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。