#P17832. [Ontak2022]REA

    ID: 16775 传统题 500~5000ms 768MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>数据结构CF2200并查集分治算法基础模拟

[Ontak2022]REA

题目描述

有一棵包含 nn 个顶点的无向树,以顶点1为根。每条边具有激活或未激活两种状态,初始全部激活。

顶点 xx 的结合数定义为:只沿激活边与 xx 连通的顶点总数,包括 xx 自己。

处理以下两类操作:

  • 1 t:把顶点 tt 与其父亲之间的边的状态取反。
  • 2 w:询问顶点 ww 的结合数。

输入格式

第一行两个整数 n,qn,q。接下来 n−1n-1 行,每行两个整数 xi,yix_i,y_i,表示树边。最后 qq 行给出操作。

输出格式

对每个类型 2 的操作输出一行结合数。类型 1 不输出。

数据范围

1≤n,q≤4000001\le n,q\le400000;边端点在 [1,n][1,n] 内;类型 1 满足 2≤t≤n2\le t\le n;类型 2 满足 1≤w≤n1\le w\le n。

子任务

子任务 附加限制 分值
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