题目描述

本题为《E.小红的根（easy）》的困难版本，两题的区别在于：本题中 $1 \leq k \leq 2\times 10^5$。 给定一棵包含 $n$ 个节点的树，小红对其有两种共 $k$ 个断言： $\hspace{23pt}\bullet\,$种类 $1$：给定两个整数 $a, b\left(a \ne b \right)$，代表节点 $a$ 是节点 $b$ 的祖先节点$^\texttt{[1]}$； $\hspace{23pt}\bullet\,$种类 $2$：给定两个整数 $a, b\left(a \ne b \right)$，代表节点 $a$ 与节点 $b$ 没有祖先关系，即节点 $a$ 不是节点 $b$ 的祖先、节点 $b$ 也不是节点 $a$ 的祖先。 请你计算，共有多少个 $i \in [1,n]$ 满足：将节点 $i$ 选为树的根后，能够满足所有的断言。 【名词解释】 祖先节点$^\texttt{[1]}$：在一棵以 $u$ 为根的树中，若点 $x$ 在 $u$ 到 $v$ 的简单路径$^\texttt{[2]}$上，且 $x \ne v$，则称 $x$ 是 $v$ 的祖先节点。根节点没有祖先节点。 简单路径$^\texttt{[2]}$：树上任意两个节点之间的路径，不经过重复的点和边。在树上，任意两个节点间有且仅有一条简单路径。官方中文

输入格式

第一行输入两个整数 $n,k\left(2 \leq n \leq 2\times 10^5;\,1 \leq k \leq 2\times 10^5\right)$。 之后的 $n - 1$ 行，第 $i$ 行输入两个整数 $u_i,v_i\left(1 \leq u_i, v_i \leq n;\, u_i \neq v_i\right)$ 表示树上第 $i$ 条边连接节点 $u_i$ 和 $v_i$。保证树连通。 之后的 $k$ 行，第 $i$ 行输入三个整数 $op_i,a_i,b_i\left( op_i\in \{1,2\};\,1 \leq a_i,b_i \leq n;\, a_i \ne b_i\right)$，代表第 $i$ 个断言的种类是 $op_i$，参数为 $a_i,b_i$。官方中文

输出格式

输出一个整数，代表符合条件的节点数量。官方中文