Quy hoạch động trên cây 1 (DP on Tree) - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	Con cháu	100 (p)	3.0s	512M
2	CSES - Tree Matching \| Cặp ghép trên cây	100 (p)	1.0s	256M
3	CSES - Tree Diameter \| Đường kính của cây	100 (p)	1.0s	256M
4	Khoảng cách dài nhất	100 (p)	3.0s	512M
5	Tổng khoảng cách	100 (p)	3.0s	512M

1. Con cháu

Điểm: 100 (p) Thời gian: 3.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một cây có \(n\) nút được đánh số từ \(1\) đến \(n\), gốc là nút \(1\). Với mỗi nút trên cây, hãy tìm số lượng con cháu của nó.

Input

Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 2 \cdot 10^5\)).
Dòng thứ hai chứa \(n-1\) số nguyên dương lần lượt là cha của mỗi nút từ \(2, 3, \dots, n\).

Output

In ra \(n\) số nguyên, số lượng con cháu của mỗi nút \(1, 2, \dots, n\).

Example

Test 1

Input

5
1 1 2 3

Output

4 1 1 0 0

Scoring

Nguồn: CSES.

2. CSES - Tree Matching | Cặp ghép trên cây

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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

Một cặp ghép là tập hợp các cạnh mà mỗi đỉnh là đầu mút của tối đa một cạnh. Hãy xác định số lượng cạnh tối đa có trong một cặp ghép.

Input

Dòng đầu tiên gồm một số \(n\): số lượng nút của cây. Các nút được đánh số theo thứ tự \(1, 2, 3, ..., n\)
\(n - 1\) dòng tiếp theo, mỗi dòng chứa 2 số \(a\) và \(b\), thể hiện rằng có một cạnh giữa 2 nút này

Constraints

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

Output

Một số nguyên duy nhất: số cặp tối đa

Example

Test 1

Input

Output

Note

Có thể lấy cạnh \((1, 2)\) và \((3, 4)\) vào cặp ghép.

3. CSES - Tree Diameter | Đường kính của cây

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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

Đường kính của cây là khoảng cách xa nhất giữa hai nút bất kì. Hãy xác định đường kính của cây.

Input

Dòng đầu chứa một số nguyên \(n\) - số lượng nút. Các đỉnh được đánh số \(1,2,3,\dots,n\)
Sau đó là \(n-1\) dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên \(a\) và \(b\) - có một cạnh nối nút \(a\) và \(b\)

Constraints

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

Output

In ra một số nguyên - đường kính của cây

Example

Test 1

Input

Output

Note

Đường kính \(3\) tương ứng với đường đi \(2 \rightarrow 1 \rightarrow 3 \rightarrow 5\)

4. Khoảng cách dài nhất

Điểm: 100 (p) Thời gian: 3.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một cây có \(n\) nút được đánh số từ \(1\) đến \(n\). Với mỗi nút trên cây, hãy tìm khoảng cách dài nhất từ nút đó đến các nút khác.

Input

Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 2 \cdot 10^5\)).
\(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(a\) và \(b\) (\(1 \le a, b \le n\)), thể hiện có cạnh nối giữa nút \(a\) và nút \(b\).

Output

In ra \(n\) số nguyên, số thứ \(i\) (\(1 \le i \le n\)) là khoảng cách dài nhất từ nút \(i\) đến các nút khác trong cây.

Example

Test 1

Input

Output

2 3 2 3 3

Scoring

Subtask \(1\) (\(50\%\) số điểm): \(n \le 10^3\).
Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

5. Tổng khoảng cách

Điểm: 100 (p) Thời gian: 3.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một cây có \(n\) nút được đánh số từ \(1\) đến \(n\). Với mỗi nút trên cây, hãy tính tổng khoảng cách từ nút đó đến tất cả các nút khác.

Input

Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 2 \cdot 10^5\)).
\(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(a\) và \(b\) (\(1 \le a, b \le n\)), thể hiện có cạnh nối giữa nút \(a\) và nút \(b\).

Output

In ra \(n\) số nguyên, số thứ \(i\) (\(1 \le i \le n\)) là tổng khoảng cách từ nút \(i\) đến các nút khác.

Example

Test 1

Input

Output

6 9 5 8 8

Constraints

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