CSES - Finding a Centroid

View as PDF
All submissions
Best submissions
Authors:
Flower_On_Stone , Elektrikar
Problem types
Points: 1600 Time limit: 1.0s Memory limit: 512M Input: stdin Output: stdout

Given a tree of \(n\) nodes, your task is to find a centroid, i.e., a node such that when it is appointed the root of the tree, each subtree has at most \(⌊n/2⌋\) nodes.

Input

  • The first input line contains an integer \(n\): the number of nodes. The nodes are numbered \(1,2,…,n\).
  • Then there are \(n−1\) lines describing the edges. Each line contains two integers \(a\) and \(b\): there is an edge between nodes \(a\) and \(b\).

Output

  • Print one integer: a centroid node. If there are several possibilities, you can choose any of them.

Constraints

  • \(1 \le n \le 2 \cdot 10^5\)
  • \(1 \le a, b \le n\)

Example

Sample input

5
1 2
2 3
3 4
3 5

Sample output

3

Comments


  • -4
    N7hoatt    5:32 p.m. 29 aug, 2023

    Cho một cây gồm \(n\) đỉnh. Hãy xác định trọng tâm của cây. Trọng tâm của một cây là một đỉnh khi nó làm gốc của cây thì mỗi cây con có nhiều nhất \(⌊n/2⌋\) đỉnh.

    Input

    • Dòng đầu tiên gồm số nguyên \(n\): số lượng đỉnh. Các đỉnh được đánh số từ \(1,2,3,\dots,n\).
    • \(n-1\) dòng sau đó biểu diễn các cạnh. Mỗi dòng gồm hai số nguyên \(a\) và \(b\): có cạnh nối giữa \(a\) và \(b\).

    Output

    • In ra một số nguyên: trọng tâm của cây. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

    Constraints

    • \(1\leq n\leq 2 \times 10^5\).
    • \(1\leq a,b\leq n\).

    Example

    Test

    Input 
    5
1 2
2 3
3 4
3 5
    Output 
    3
    Note
    2 replies