题目描述

游戏《异锁》的地图可以看作一棵由 $n$ 个点和 $n-1$ 条双向道路组成的树，点的编号为 $1,2,\ldots,n$。 当比利在点 $c$ 释放技能“锁链囚徒”时，他会用锁链拴住敌人，并将其拉向自己！若敌人位于点 $u\ne c$，则敌人会被拉到从 $u$ 到 $c$ 的简单路径上，从 $u$ 出发的下一个点 $v$。若其已位于点 $c$，则敌人会留在原地。 这么超模的技能当然也有办法反制。每次释放技能时，都会出现一个由编号区间 $l,r$ 指定的破绽区域，即所有编号满足 $l\le u\le r$ 的点。当且仅当敌人位于破绽区域内的点 $u$，且原本会被拉到的点 $v$ 在破绽区域外时，敌人的锁链会断裂。 比利将释放 $m$ 次“锁链囚徒”。第 $i$ 次释放时，他位于点 $c_i$，破绽区域由区间 $l_i,r_i$ 指定。对于每次释放技能，比利想知道有多少个点 $u$，使得若一名敌人在技能释放前位于点 $u$，其锁链会断裂？由于比利正在忙着挥舞他的狼牙棒，所以这个问题需要你来回答。官方中文

输入格式

第一行输入两个正整数 $n,m\left(1\le n,m\le 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$。 接下来 $m$ 行，每行包含三个正整数 $c_i,l_i,r_i\left(1\le c_i\le n;\,1\le l_i\le r_i\le n\right)$，表示一次技能释放：比利位于点 $c_i$，破绽区域为编号区间 $[l_i,r_i]$。官方中文

输出格式

对于每次询问，新起一行输出一个非负整数，表示敌人站在该位置时锁链会断裂的位置数量。官方中文