A13431 | Nested Rubber Bands
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
You have a tree of $n$ vertices. You are going to convert this tree into $n$ rubber bands on infinitely large plane. Conversion rule follows:
- For every pair of vertices $a$ and $b$ , rubber bands $a$ and $b$ should intersect if and only if there is an edge exists between $a$ and $b$ in the tree.
- Shape of rubber bands must be a simple loop. In other words, rubber band is a loop which doesn't self-intersect.
Now let's define following things:
- Rubber band $a$ includes rubber band $b$ , if and only if rubber band $b$ is in rubber band $a$ 's area, and they don't intersect each other.
- Sequence of rubber bands $a_{1}, a_{2}, \ldots, a_{k}$ ( $k \ge 2$ ) are nested, if and only if for all $i$ ( $2 \le i \le k$ ), $a_{i-1}$ includes $a_{i}$ .
 This is an example of conversion. Note that rubber bands $5$ and $6$ are nested. It can be proved that is it possible to make a conversion and sequence of nested rubber bands under given constraints.
What is the maximum length of sequence of nested rubber bands can be obtained from given tree? Find and print it.
- For every pair of vertices $a$ and $b$ , rubber bands $a$ and $b$ should intersect if and only if there is an edge exists between $a$ and $b$ in the tree.
- Shape of rubber bands must be a simple loop. In other words, rubber band is a loop which doesn't self-intersect.
Now let's define following things:
- Rubber band $a$ includes rubber band $b$ , if and only if rubber band $b$ is in rubber band $a$ 's area, and they don't intersect each other.
- Sequence of rubber bands $a_{1}, a_{2}, \ldots, a_{k}$ ( $k \ge 2$ ) are nested, if and only if for all $i$ ( $2 \le i \le k$ ), $a_{i-1}$ includes $a_{i}$ .
 This is an example of conversion. Note that rubber bands $5$ and $6$ are nested. It can be proved that is it possible to make a conversion and sequence of nested rubber bands under given constraints.
What is the maximum length of sequence of nested rubber bands can be obtained from given tree? Find and print it.
输入格式
The first line contains integer $n$ ( $3 \le n \le 10^{5}$ ) — the number of vertices in tree.
The $i$ -th of the next $n-1$ lines contains two integers $a_{i}$ and $b_{i}$ ( $1 \le a_{i} \lt b_{i} \le n$ ) — it means there is an edge between $a_{i}$ and $b_{i}$ . It is guaranteed that given graph forms tree of $n$ vertices.
The $i$ -th of the next $n-1$ lines contains two integers $a_{i}$ and $b_{i}$ ( $1 \le a_{i} \lt b_{i} \le n$ ) — it means there is an edge between $a_{i}$ and $b_{i}$ . It is guaranteed that given graph forms tree of $n$ vertices.
输出格式
Print the answer.
输入输出样例
输入 #1
6 1 3 2 3 3 4 4 5 4 6
输出 #1
4
输入 #2
4 1 2 2 3 3 4
输出 #2
2
In the first sample, you can obtain a nested sequence of $4$ rubber bands( $1$ , $2$ , $5$ , and $6$ ) by the conversion shown below. Of course, there are other conversions exist to make a nested sequence of $4$ rubber bands. However, you cannot make sequence of $5$ or more nested rubber bands with given tree.
You can see one of the possible conversions for the second sample below.

You can see one of the possible conversions for the second sample below.

C++ 编辑器
输入
输出
可保存默认模板;新题优先使用已保存模板。
当前快捷键仅展示,暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好,我是作答助手。可以问思路、复杂度、样例含义或代码报错原因;不会直接给出完整 AC 代码。
确定要清空代码吗?
提交通过
评测结果:Accepted