#P17832. [Ontak2022]REA
[Ontak2022]REA
题目描述
有一棵包含 个顶点的无向树,以顶点1为根。每条边具有激活或未激活两种状态,初始全部激活。
顶点 的结合数定义为:只沿激活边与 连通的顶点总数,包括 自己。
处理以下两类操作:
1 t:把顶点 与其父亲之间的边的状态取反。2 w:询问顶点 的结合数。
输入格式
第一行两个整数 。接下来 行,每行两个整数 ,表示树边。最后 行给出操作。
输出格式
对每个类型 2 的操作输出一行结合数。类型 1 不输出。
数据范围
;边端点在 内;类型 1 满足 ;类型 2 满足 。
子任务
| 子任务 | 附加限制 | 分值 |
|---|---|---|
| 1 | n≤20,q≤300 | 5 |
| 2 | n·q≤10⁷ | 20 |
| 3 | 树是一条链 | 10 |
| 4 | 树是星形 | |
| 5 | n,q≤100000 | 20 |
| 6 | 无额外限制 | 35 |
样例 1
输入:
6 8
1 2
1 3
2 4
2 6
3 5
2 6
1 3
2 3
1 3
2 5
1 2
2 1
2 2
输出:
6
2
6
3
3