问题 E: 黄金树叶(tree)

时间限制: 3.000 Sec 内存限制: 256 MB

提交: 16 解决: 5

题目描述

忍者村中有一颗传承百年的参天大树，该树只会在春天长出绿色的树叶，到秋天树叶开始慢慢变黄。变黄的树叶颜色惊艳无比，因此这棵树的落叶也被称为黄金树叶。更加神奇的是，这棵树的树叶变黄是从下往上发生的。也就是说，每到秋天，从远望去，树的上半部分都是绿色，下半部分都是黄色。

为了更加充分地感受黄金树叶之美，现在你需要统计树上黄色叶子的个数。

为了方便讨论，我们认为该树是一颗有n 个节点的有根树，根节点标号为1，根节点的深度为1，最开始整棵树的所有节点都是绿的。

现在一共有 m 个操作，操作有两种。

1. 将整棵树都染绿，之后让深度 $\ge x$的节点都变黄。

2. 询问一个节点 x 的子树中有多少个黄色节点。

输入格式

第一行输入两个正整数n和m，分别表示树的节点个数和操作个数。

接下来输入n-1行，每行两个正整数x,y，表示树上的一条边。

接下来 m 行，每行两个正整树 op,x (1<=x<=n)，如果 op=1 表示操作一，否则表示操作二。

输出格式

对于每个操作二，输出一行一个正整数，表示 x的子树中黄色节点的个数。

样例输入

5 9
1 2
1 3
2 4
4 5
1 3
2 5
2 2
2 1
1 2
2 1
2 4
2 5
2 2

样例输出

1
2
2
4
2
1
3

提示

【数据范围】

30%的数据保证，$1\le n \le 1000,1\le m\le1000$

100%的数据保证，$1\le n\le10^5,1\le m\le10^5$