CSES - Tree Distances I | Khoảng cách trên cây I

View as PDF
All submissions
Best submissions
Authors:
Flower_On_Stone , Elektrikar
Problem type
Points: 1500 (p) Time limit: 1.0s Memory limit: 512M Input: stdin Output: stdout

You are given a tree consisting of \(n\) nodes.

Your task is to determine for each node the maximum distance to another node.

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 \(n\) integers: for each node \(1,2,…,n\), the maximum distance to another node.

Constraints

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

Example

Sample input

5
1 2
1 3
3 4
3 5

Sample output

2 3 2 3 3

Comments


  • 0
    N7hoatt    11:08 a.m. 17 aug, 2023

    Cho một cây gồm \(n\) đỉnh.

    Với mỗi đỉnh, hãy tìm khoảng cách lớn nhất từ đỉnh đó tới một đỉnh khác.

    Input

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

    Output

    • In ra \(n\) số nguyên: với mỗi đỉnh \(1,2,3,\dots,n\), in ra khoảng cách lớn nhất tới một đỉnh khác.

    Constraints

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

    Example

    Test

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