题目描述

给定一棵包含 $n$ 个顶点的树，顶点编号为 $1,2,\ldots,n$。每个顶点被染成 $b$ 种颜色之一，颜色用 $1,2,\ldots,b$ 表示。

称顶点子集 $A\subseteq\{1,2,\ldots,n\}$ 是一个 美丽子集，当且仅当：

1. $A$ 中所有顶点的颜色相同；
2. 树中存在一条简单路径，能够经过 $A$ 中的所有顶点。该路径也可以经过不属于 $A$ 的顶点。

请对每一种颜色，求出由该颜色顶点构成的最大美丽子集的大小。

下图是样例一对应的树，其中 $n=11$，$b=3$。

输入格式

第一行包含两个整数 $n,b$，分别表示树的顶点数和颜色数。

后续输入格式取决于 $n$ 的大小。

当 $n\le 200000$ 时

接下来输入 $n$ 行。第 $i$ 行包含两个整数 $p_i,c_i$，表示：

• 顶点 $i$ 的父亲为 $p_i$；
• 顶点 $i$ 的颜色为 $c_i$。

如果顶点 $i$ 是树根，则 $p_i=0$。

当 $n>200000$ 时

接下来仅输入一行，其中包含七个整数：

$$A,B,M,K,A',B',M'.$$

这些整数均在 $1$ 到 $10^9$ 之间。它们定义两个数列：

$$r_0=0,\qquad r_{i+1}=(A\cdot r_i+B)\bmod M,$$

以及

$$r'_0=0,\qquad r'_{i+1}=(A'\cdot r'_i+B')\bmod M'.$$

此时树及其染色按如下方式生成：

• 顶点 $1$ 是树根，即 $p_1=0$；
• 对每个 $i=2,3,\ldots,n$，令

$$p_i=i-1-\bigl(r_i\bmod \min(K,i-1)\bigr);$$

• 对每个 $i=1,2,\ldots,n$，令

$$c_i=1+(r'_i\bmod b).$$

采用这种生成方式，是为了在不读入海量数据的情况下表示一棵规模很大的、近似随机的树。

输出格式

设 $\ell_i$ 表示颜色 $i$ 的最大美丽子集大小。输出格式同样取决于 $n$ 的大小。

当 $n\le 200000$ 时

输出 $b$ 行，第 $i$ 行输出 $\ell_i$。

当 $n>200000$ 时

输出一行，包含：

$$\ell_1+\ell_2+\cdots+\ell_b.$$

这一要求用于避免在超大测试中产生过多输出。

数据范围

• $1\le b\le n\le 5\,000\,000$；
• 对每个顶点 $i$，除树根满足 $p_i=0$ 外，其余顶点满足 $1\le p_i\le n$；
• $1\le c_i\le b$；
• 所有父子边构成一棵树。

子任务

子任务	分值	限制
1	25	$n\le 20$
2		$n\le 1000$
3	30	$n\le 200000$
4	20	无额外限制

样例一

输入

11 3
9 2
8 1
1 1
0 3
9 2
8 3
1 1
4 3
4 1
2 2
9 3

输出

3
2
4

样例二

输入

200001 123
7 17 11 2 19 3 13

输出

120010

样例说明

样例一中，对于颜色 $1$，顶点集合 $\{2,7,9\}$ 是一个美丽子集，因为简单路径

$$2\to 8\to 4\to 9\to 1\to 7$$

经过了这三个顶点。