| 题目名称 | 2274. [HEOI2016/TJOI2016]树 |
|---|---|
| 输入输出 | heoi2016_tree.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 stdafx.h
于2016-04-24加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：166， 提交：337， 通过率：49.26% | ||||
 AAAAAAAAAA |
100 | 0.076 s | 0.32 MiB | C++ |
 Hzoi_chairman |
100 | 0.080 s | 0.32 MiB | C++ |
|
Hzoi_chairman |
100 | 0.091 s | 0.32 MiB | C++ |
 LCWhiStLe |
100 | 0.093 s | 0.80 MiB | C++ |
 Hzoi_Mafia |
100 | 0.094 s | 0.81 MiB | C++ |
 _Itachi |
100 | 0.099 s | 0.22 MiB | C++ |
 GROWL GOOD BOYส็ |
100 | 0.099 s | 0.43 MiB | C++ |
 AntiLeaf |
100 | 0.102 s | 0.93 MiB | C++ |
|
AntiLeaf |
100 | 0.103 s | 13.77 MiB | C++ |
|
GROWL GOOD BOYส็ |
100 | 0.104 s | 0.32 MiB | C++ |
| 本题关联比赛 | |||
| 并查集专题 | |||
| 关于 树 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
没路径压缩的并查集暴力标记都能过 好水啊
| ||||
|
O(n^2)的算法，为什么AC的那么多？
| ||||
|
嗯..直接上没路径压缩的并查集暴力打标记AC..
果然大力出奇迹  HyOI_Dhy
2017-12-03 19:38
26楼
| ||||
|
wow
暴力70 加个0 wow 暴力100  CSU_Turkey
2017-11-19 11:07
25楼
| ||||
|
hahahahaha,果然是乱搞出奇迹
| ||||
|
这题不是在逗我吗= =
| ||||
|
打标记AC
| ||||
|
| ||||
|
样例
5 5 1 2 1 3 2 4 2 5 Q 2 C 2 Q 2 Q 5 Q 3  Ostmbh
2017-05-11 21:03
20楼
| ||||
|
mmp... 啪啪啪啪
 Fisher.
2017-05-10 21:02
19楼
| ||||
AeeE5x
HtBest
Letter zZZz
xzz_2332274. [HEOI2016/TJOI2016]树
★☆ 输入文件：heoi2016_tree.in
输出文件：heoi2016_tree.out
简单对比时间限制：1 s 内存限制：128 MiB
【题目描述】
在 2016 年，佳媛姐姐刚刚学习了树，非常开心。现在她想解决这样一个问题：给定一颗有根树，根为 $1$，有以下两种操作：
1. 标记操作：对某个结点打上标记。（在最开始，只有结点 $1$ 有标记，其他结点均无标记，而且对于某个结点，可以打多次标记。）
2. 询问操作：询问某个结点最近的一个打了标记的祖先（这个结点本身也算自己的祖先）。
你能帮帮她吗？
【输入格式】
第一行两个正整数 $N$ 和 $Q$ 分别表示节点个数和操作次数。
接下来 $N-1$ 行，每行两个正整数 $u,v$（$1 \leq u,v \leq n$）表示 $u$ 到 $v$ 有一条有向边。
接下来 $Q$ 行，形如 oper num，oper 为 C 时表示这是一个标记操作，oper 为 Q 时表示这是一个询问操作。
【输出格式】
对于每个询问操作，输出一行，一个正整数，表示结果。
【样例 1 输入】
5 5 1 2 1 3 2 4 2 5 Q 2 C 2 Q 2 Q 5 Q 3
【样例 1 输出】
1 2 2 1
【数据范围】
$30\%$ 的数据，$1 \leq N, Q \leq 1000$；
$70\%$ 的数据，$1 \leq N, Q \leq 10000$；
$100\%$ 的数据，$1 \leq N, Q \leq 100000$。