CSP1265. 灯（light）

\r\n

时限: 3000 ms | 内存: 1024 MB | 难度: 9

\r\n

灯

\r\n

题目描述

\r\n

小 Z 买了一个大房子，房子里有 $n$ 个房间，每个房间都配有 1 盏灯，这 $n$ 个房间由 $n - 1$ 条通道相连，其中 1 号房间是主房间。换言之，小 Z 的房子构成了以 1 为根的树形结构。由于房子太大，小 Z 为了更好的监控用电情况，在每个房间都加装了电表，每个房间的电表会统计这个房间树形结构下所有以它为祖先的房间的用电量。换言之，如果一个房间产生用电的话（即房间的灯是亮着的），那么该房间到 1 号房间路径上的所有房间电表用电量都会变化。

\r\n

小 Z 记录了自己一段时间内房间的开关灯情况，最开始所有房间的灯都是关闭的。同时小 Z 也会不定时去检查某一层所有电表的变化情况。

\r\n

小 Z 把这一段时间的记录交给了你，请你帮助他来回答这些问题。

\r\n

输入格式

\r\n

从 light.in 文件读入数据。

\r\n

第一行包含两个整数 $n$ 和 $q$，分别表示房间数量和操作次数。

\r\n

接下来 $(n - 1)$ 行，第 $i$ 行输入两个整数 $u_i$ 和 $v_i(1\\le u_i,v_i\\le n)$ 表示一条连接房间 $u_i$ 与 $v_i$ 的边。

\r\n

接下来 $q$ 行，每行输入两个整数 $t,x$，其中 $t = 1$ 时，表示小 Z 改变了房间 $x$ 灯的开关状态；$t = 2$ 时，表示小 Z 查询第 $x$ 层有多少电表用电量在变化。

\r\n

输出格式

\r\n

输出到 light.out 文件。

\r\n

对于每个 $t = 2$ 的操作，输出一行一个整数。

\r\n

样例 #1

\r\n

样例输入 #1

\r\n

7 10\r\n1 2\r\n1 3\r\n2 4 \r\n2 5\r\n3 6\r\n6 7\r\n1 1\r\n2 1\r\n1 1\r\n1 2 \r\n1 3\r\n2 2\r\n2 1\r\n1 3\r\n1 7\r\n2 2\r\n

\r\n

Copy

\r\n

样例输出 #1

\r\n

1\r\n2 \r\n1\r\n2\r\n

\r\n

Copy

\r\n

提示

\r\n

【样例 1 解释】

\r\n

第一次查询时，只有 1 号点的灯亮着，查询第一层，所以也只有 1 号房间的电表在变化。

\r\n

第二次查询时，只有 2，3 号灯在亮着，查询第二层，所以有第 2，3 号的房间电表在变化。

\r\n

第三次查询时，只有 2，3 号灯在亮着，查询第一层，因为 1 号房间是 2，3 号房间的上层房间，所以 1 号房间的电表同样在变化。

\r\n

第四次查询时，只有 2，7 号灯在亮着，查询第二层，因为 3 号房间是 7 号房间的上层房间，所以第二层两个房间的电表都在变化。

\r\n

样例 2～ 5 都可以点击链接 light_sample.zip 下载大样例压缩包，具体如下。

\r\n

【样例 2】

\r\n

见附件的 light_sample2.in 与 light_sample2.ans。

\r\n

【样例 3】

\r\n

见附件的 light_sample3.in 与 light_sample3.ans。

\r\n

【样例 4】

\r\n

见附件的 light_sample4.in 与 light_sample4.ans。

\r\n

【样例 5】

\r\n

见附件的 light_sample5.in 与 light_sample5.ans。

\r\n

【数据范围】

\r\n

对于 $30\\%$ 的数据，满足 $2\\le n,q \\le 5000$；

\r\n

另有 $10\\%$ 的数据，满足特殊性质 A;

\r\n

另有 $10\\%$ 的数据，满足特殊性质 B;

\r\n

对于 $80\\%$ 的数据，满足 $2\\le n,q\\le 10^5$

\r\n

对于 $100\\%$ 的数据，满足 $2\\le n,q\\le 5\\times10^5$。

\r\n

\r\n
特殊性质 A: 对于任意的 $i(1\\le i \\le n - 1)$，都有 $u_i = i,v_i = i + 1$。
\r\n
\r\n
特殊性质 B: 满足所有 $t = 2$ 的操作在 $t = 1$ 的操作之后。
\r\n

统计

递交统计

CSP1265. 灯（light）

信息

还没有账户？

登录