U177650 【模板】Euler - Tour - Tree

优秀的 顶树 也能过。 艹，这是轻工业，请不要把这道题当重工业的测试。期望复杂度是 $\mathcal O(n\log n)$

你需要一个数据结构维护一棵树的以下操作。 - 换根。 - 子树乘。 - 换爸爸。 - 询问子树和对 $p$ 取余后的值。

第一行三个整数 $n,m,mod$ 表示树点数，操作数，取余数。 接下来 $n-1$ 行每行两个数表示一条树边。 第 $n+1$ 行 $n$ 个数表示初始点权。 接下来 $m$ 行，每行格式如下： - $opt=1$，后面跟一个整数表示目标换的根。 - $opt=2$，后面跟两个整数 $x,val$ 表示对于 $x$ 子树乘 $val$，$x$ 不为根。 - $opt=3$，后面跟两个整数 $x,y$ 表示将 $x$ 的父亲换为 $y$，$x$ 深度大于二。 - $opt=4$，后面跟一个整数表示询问子树和，不为根。

对于每个 $4$ 操作输出答案。

请大胆使用多项式算法，1s，512MB。 对于所有数据有 $n,m\leq10^{5}，mod\le2\times10^{9}$ | 部分分 | 性质 | 分数 | | --------- | ----------------------------- | ---- | | subtask 1 | $n,m\le 1000$ | 6 | | subtask 2 | 没有 3 操作。 | 12 | | subtask 3 | 没有 1 操作。 | 19 | | subtask 4 | $opt=2$ 时 $val=0$。 | 12 | | subtask 5 | $mod$ 为质数。 | 23 | | subtask 6 | $n,m\le10^{5}$ | 28 | 只放置了最后两个 SUB。