思路

输入中的父亲和颜色需要先严格按给定的线性同余过程还原。因为每个父亲编号都小于儿子编号，所以可以从大编号向小编号累加子树大小，并同时选出每个顶点的重儿子。

对一个当前维护的顶点集合，记某种颜色出现了多少次。再维护“出现次数等于某个值的颜色数”。这样，加入或删除一个顶点时只会让一种颜色的出现次数改变一，并且可以同时得到当前最大出现次数以及达到该次数的颜色数。

做法

对树求一遍深度优先序，使每棵子树对应序列中的一个连续区间。随后执行启发式合并：先处理所有轻儿子且不保留其统计信息，再处理重儿子并保留其统计信息；之后把所有轻儿子子树的区间和当前顶点加入。此时维护的集合恰好是当前顶点的整棵子树，可以直接得到该顶点对应的 $m$ 和 $k$。

题目允许前 $M$ 个父亲形成很深的链，因此深度优先遍历和启发式合并都使用显式栈实现，避免递归栈溢出。

对于第一档限制，可以逐个处理根的儿子。每个这样的子树只包含该儿子及若干叶子，所有子树互不相交，因此用一张可清空的颜色计数表即可在线性时间内求出全部答案。

对于第二档限制，设不同颜色数为 $C$。固定一种颜色，先标记每个顶点是否为该颜色，再按编号从大到小把计数累加到父亲，就能得到这种颜色在每棵子树中的出现次数。枚举全部颜色并更新各顶点的最大值与并列颜色数即可。

正确性证明

首先证明启发式合并过程中统计集合的含义。所有轻儿子在处理完成后都会删除自己的统计信息，因此处理重儿子之前集合为空；重儿子处理完成后，其整棵子树被保留。随后加入每棵轻儿子的整棵子树以及当前顶点。不同儿子子树互不相交，所以加入结束后，集合恰好包含当前顶点子树中的每个顶点一次。

颜色计数表记录集合中每种颜色的出现次数，而次数桶记录每个正出现次数对应多少种颜色。因此其最大非空次数就是 $m$，该桶的大小就是 $k$。由上一段可知，在记录顶点答案时集合恰好是该顶点的子树，所以得到的 $m,k$ 正确。

对每个顶点递归关系相同，叶子显然成立，按处理顺序归纳即可证明所有顶点的答案均正确。最后逐项按题意计算异或、乘积与模数，故输出值正确。

复杂度

每当一个顶点因轻边被重新加入时，它所在子树的规模至少翻倍，因此每个顶点被加入或删除 $O(\log N)$ 次。总时间复杂度为 $O(N\log N)$，空间复杂度为 $O(N)$。