| 题目名称 | 2701. 动态树 |
|---|---|
| 输入输出 | dynamic_tree.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 FoolMike
于2017-06-09加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：73， 提交：175， 通过率：41.71% | ||||
 rewine |
100 | 0.513 s | 8.32 MiB | C++ |
 AAAAAAAAAA |
100 | 0.707 s | 10.34 MiB | C++ |
 Kirin |
100 | 0.771 s | 4.87 MiB | C++ |
 1592063346 |
100 | 0.812 s | 5.65 MiB | C++ |
|
AAAAAAAAAA |
100 | 0.859 s | 3.94 MiB | C++ |
 Hale |
100 | 0.892 s | 24.34 MiB | C++ |
 小一米 |
100 | 0.897 s | 5.08 MiB | C++ |
|
小一米 |
100 | 0.899 s | 5.08 MiB | C++ |
 y_immortal |
100 | 0.909 s | 12.52 MiB | C++ |
 dsl2002 |
100 | 0.910 s | 5.85 MiB | C++ |
| 关于 动态树 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
看错题+手残
AAAAAAAAAA
2018-01-22 17:32
7楼
| ||||
|
数据应该是随机的,暴力可过
rewine
2017-07-16 07:27
6楼
| ||||
|
维护子树信息等于模板+4行。。。。
 再见
2017-06-24 13:01
5楼
| ||||
|
回复 @_Itachi :
每次暴力dfs求子树大小……我交了一下暴力，发现得了70分…… | ||||
|
原本以为Mike大爷又想出了什么神奇的东西，没想到就是裸的LCT维护子树信息
 小一米
2017-06-10 11:39
3楼
| ||||
|
回复 @常可神犇2017高夺魁 :
看这数据范围，您是指LCT是暴力吗？  _Itachi
2017-06-09 20:54
2楼
| ||||
|
数据有点弱啊，自己写的暴力能跑70分，再来点wys是不是就踩标算了啊……
 FoolMike
2017-06-09 14:25
1楼
| ||||
【题目描述】
开始时有n个点形成的森林，共m个操作。
tp=1时，接下来一个参数u，表示将u所在的树树根变为u。
tp=2时，接下来一个参数u，询问以u为根的子树的大小。
tp=3时，接下来两个参数u,v，添加一条边(u,v)，并将u所在树的根作为两棵树合并后的根。
【输入格式】
第一行两个整数n,m。
接下来m行，每行开头是一个整数tp。tp=1或tp=2时，接下来一个整数u。tp=3时，接下来两个整数(u,v)。
【输出格式】
对于每个询问，你需要输出以u为根的子树大小。
【样例输入】
5 10 3 2 3 3 4 5 3 2 4 2 1 2 5 3 1 2 2 4 1 3 2 1 2 4
【样例输出】
1 1 2 1 2
【数据范围】
n<=200000,m<=400000
【来源】
Mike的脑洞