問題一覧 > 通常問題

No.763 Noel-chan and Playing with Trees

レベル : / AI推定難易度 : 1150 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 182
作問者 : polylogK / テスター : drken1215
お気に入りにしたユーザー ProblemId : 2143 / 自分の提出
問題文最終更新日: 2018-12-23 21:03:06
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2018 (順位表) の他の問題:

Problem Statement

One day, Noel-chan found a tree.
Noel-chan wants to delete some vertices from the tree she found to increase the number of trees.
Find the maximum possible number of connected components after choosing and deleting 0 or more vertices from the tree.
(Problem statement corrected on 2018/12/23; the meaning of the problem has not changed.)

Input

$N$
$U_1\ \ V_1$
$U_2\ \ V_2$
$\vdots$
$U_{N-2}\ \ V_{N - 2}$
$U_{N-1}\ \ V_{N - 1}$

The first line contains the number of vertices of the tree, $N(1\le N\le 10^5)$.
Each of the following $N - 1$ lines contains the endpoints of an edge, $U_i, V_i(1\le U_i, V_i \le N)$.

Output

Output the maximum value on one line.

Sample

Sample 1
Input
5
1 2
2 3
3 4
4 5
Output
3

Delete vertices 2, 4 (corrected 12/11 05:00)

Sample 2
Input
7
1 2
1 3
2 4
2 5
3 6
3 7
Output
5

Delete vertices 2, 3.

Sample 3
Input
12
1 2
2 3
3 4
4 5
1 6
6 7
6 8
7 11
7 12
8 9
9 10
Output
7

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。