T194631 C. 买【NOIP 计划 · 模拟赛 #4】

给定一棵 $n$ 个节点的西瓜树，第 $i$ 个点的编号为 $i$，第 $j$ 条边的编号为 $j$。 有 $m$ 次查询，每次给出 $l,r$，查询如果只保留树上点编号在 $[l,r]$ 内的点，边编号在 $[l,r]$ 内的边，有多少点连通块，此时点 $a$ 与 $b$ 连通等价于 $l \le a,b \le r$ 且 $a,b$ 在树上的简单路径中所有点与边编号都在 $[l,r]$ 之间。

第一行两个数 $n,m$。 之后 $n-1$ 行，编号从 $1$ 开始，第 $i$ 行三个数 $x,y$ 表示编号为 $i$ 的边连接着点 $x,y$。 之后 $m$ 行，每行两个数 $l,r$ 表示询问区间 $[l,r]$。

对每次询问输出一行一个数表示答案。

对于其中 $30\%$ 的数据，$n,m\le1000$。 对于其中 $50\%$ 的数据，$n\le1000$。 对于另外 $20\%$ 的数据，$n,m\le100000$。 对于 $100\%$ 的数据，满足 $1\le n,m\le1000000$，$1\le l\le r\le n$。