芙莉莲的魔导书
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

    按照芙莉莲的研究,人类魔法按照难度构成一棵树,树根为 1 号节点,人类对魔法的理解随时在演进,因此芙莉莲会对这棵树做并修改标记。
    树上编号为 i 的节点有标记 a_i,初始均为 0
    你需要维护两种操作:
  • 芙莉莲会指定编号为 x 的节点,将以这个节点为根的子树的所有非叶节点标记改为 y,叶子节点标记改为 z
  • 芙莉莲查询标记为 x 的节点有多少个,你需要给出回答。

输入描述:

    本题有多组数据,输入数据第一行一个正整数 T (1 \le T \le 10^5),表示数据组数。
    对于每组数据:
    第一行包含两个整数 n (1 \le n \le 10^5)q (1 \le n \le 10^5),其中 n 表示节点数量,q 表示操作数量。
    接下来 n - 1 行,每行包含两个整数 u, v (1 \le u, v \le n),表示树上的一条边。
    接下来 q 行每行包含 24 个整数,表示一个操作,具体如下:
    ● \verb|1 x y z| (1 \le x \le n, 0 \le y,z \le 10^9):指定编号为 x 的节点,将以这个节点为根的子树的所有非叶节点标记改为 y,叶子节点标记改为 z
    ● \verb|2 x| (0 \le x \le 10^9):查询标记为 x 的节点有多少个。
    保证所有数据中 nq 之和均不超过 10^5

输出描述:

    对于每个 \verb|2| 操作,输出一个数作为回答。
示例1

输入

复制
1
5 7
1 2
1 3
2 4
1 5
1 4 1 0
2 3
2 3
2 0
1 1 3 0
2 3
2 0

输出

复制
0
0
5
2
3