dfs序+分块求众数

铅导体

问题描述 何老板要求第三题要很简单，最好是铅导体的难度。 于是，nodgd把N个铅块用N−1根导线相连，就形成了一个铅导体。只要是在这个基础上出题，就符合何老板的要求。nodgd为了方便，就把其中的一个铅块固定在了墙上，其他铅块在导线的作用下自然下垂。每个铅块有个固定的纯度，若干个相同纯度的铅块可以聚变发电，发电的电压与铅块的数量成正比。每当nodgd需要电疗的时候，就在铅导体上选一个铅块，把它和挂在它下面的所有铅块都取下来，在这当中选一些纯度相同的铅块发电，发电之后将这些铅块挂回原来的位置。nodgd希望电疗的电压越高越好，在电压相同的情况下，nodgd又希望使用纯度更低的铅块。 但是ciocio经常来捣乱，他时不时的把整个铅导体取下来，重新选一个铅块固定到墙上，其他的铅块继续自然下垂。那么问题来了，nodgd每次都想享受最高电压的电疗，需要你大声喊出应该使用多少个纯度是多 少的铅块。

输入格式 输入文件C.in。 第一行四个整数N, A, Q, I，表示铅块的数量、铅块纯度的范围、操作的总次数、测试点编号。 铅块按1 ∼ N编号，一开始nodgd把编号为1的铅块固定在墙上。铅块的纯度是1 ∼ A之间的一个整 数。 接下来N − 1行，每行两个整数u, v，表示有一条导线连接。 接下来一行，N个整数，表示每个铅块的纯度。 接下来Q行，每行输入两个整数op, u。 若op = 1，表示ciocio把整个铅导体取下来，再把编号为u的铅块重新固定在墙上。 若op = 2，表示nodgd把编号为u的铅块以及挂在他下面的所有铅块暂时取下来，选出其中一些铅块进行聚变发电。如果要求该组测试点要求强制在线，设上一次输出的答案两个数分别为lasta和lastb，则u′ = (u+lasta×23 + lastb×233)%N + 1才是真正的节点编号。

输出格式 输出文件C.out。 每次op = 2的时候输出一行，两个整数，分别是使用铅块的纯度和数量。

样例输入 5 3 8 0 1 2 1 3 3 4 3 5 1 1 2 2 3 2 3 2 1 2 5 1 3 2 4 2 2 2 1 2 3

样例输出 2 2 1 2 3 1 2 1 1 1 1 2 1 2

数据范围

dfs序+分块求众数，很机智的一个做法将新编号对应的纯度数组复制一遍，处理根在子树内就会方便很多。