题目名称 咕咕咕 毒瘤最优化 小清新最优化
题目类型 传统型 传统型 传统型
目录 catch min easy
可执行文件名 catch min easy
输入文件名 catch.in min.in easy.in
输出文件名 catch.out min.out easy.out
每个测试点时限 1.0 秒 1.0 秒 1.0 秒
内存限制 512 MB 512 MB 512 MB
测试点/包数目 10 10 10
测试点是否等分

提交源程序文件名

对于 C++ 语言 catch.cpp min.cpp easy.cpp
对于 C 语言 catch.c min.c easy.c
对于 Pascal 语言 catch.pas min.pas easy.pas

编译选项

对于 C++ 语言 -O2 -std=c++14
对于 C 语言 -O2 -std=c14
对于 Pascal 语言 -O2

咕咕咕(catch)

【题目背景】

NOIP2019 即将到来,一个新的轮回就要开始。新时代的 OIer:加油,未来是你 们的!

【题目描述】

鸽子 AChen 准备咕掉 day2 的题目,作为一名正义的 OIer,你要用鸽子固定器使 AChen 不能咕咕咕。
具体而言,给出一棵有根树 T,AChen 在一号节点(根节点),每个单位时间 AChen 可以沿树边移动到一个相邻的节点或者停留在原地,当 AChen 到达叶子的时候如果仍 然没有被固定,他就会咕掉 day2 的试题。
你可以在任意的叶子结点放置鸽子固定器。由于这是 hycc 设计的黑科技,固定器 可以像 AChen 一样在每个单位时间移动到相邻的节点(也可以停留在原地)。
假定 hycc 制定的 AI 足够聪明,那么最少用多少个固定器可以保证 day2 不被咕 掉呢?

【输入格式】

从文件 catch.in 中读入数据。
输入的第一行包含一个正整数 n,保证 n ≤ 1000000,表示树的节点总数。
第二行至第 n 行,每行两个整数 u, v,表示树的一条边。

【输出格式】

输出到文件 catch.out 中。
输出一个整数,表示最少的固定器数目。

【样例 1 输入】

5
1 2
2 3
3 4
4 5

【样例 1 输出】

1

发表评论

电子邮件地址不会被公开。