Một ít cây cỏ - Bộ đề bài - LQDOJ: Le Quy Don Online Judge

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	Nước lạnh	100 (p)	1.0s	256M
2	CSES - Tree Diameter \| Đường kính của cây	100 (p)	1.0s	256M
3	CSES - Company Queries I \| Truy vấn công ty I	100 (p)	1.0s	512M
4	CSES - Subordinates \| Cấp dưới	100 (p)	1.0s	512M
5	CSES - Counting Paths \| Đếm đường đi	100 (p)	1.0s	512M

1. Nước lạnh

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

Mùa hè oi ả ở Wisconsin đã khiến cho lũ bò phải đi tìm nước để làm dịu đi cơn khát. Các đường ống dẫn nước của nông dân John đã dẫn nước lạnh vào 1 tập \(N\) nhánh (đánh số từ \(1...N\)) từ một cái bơm đặt ở chuồng bò.

Khi nước lạnh chảy qua các ống, sức nóng mùa hè sẽ làm nước ấm lên. Bessie muốn tìm chỗ có nước lạnh nhất để cô bò có thể tận hưởng mùa hè một cách thoải mái nhất.

Bessie đã vẽ sơ đồ toàn bộ các nhánh ống nước và nhận ra rằng nó là một đồ thị dạng cây với gốc là chuồng bò và ở các điểm nút ống thì có chính xác \(2\) nhánh con đi ra từ nút đó. Một điều ngạc nhiên là các nhánh ống này đều có độ dài là \(1\).

Cho bản đồ các ống nước, hãy cho biết khoảng cách từ chuồng bò tới tất cả các nút ống và ở các phần cuối đường ống.

"Phần cuối" của một đường ống, có thể là đi vào một nút ống hoặc là bị bịt, được gọi theo số thứ tự của đường ống. Bản đồ có \(C\) nút ống, được mô tả bằng \(3\) số nguyên: là "phần cuối" của ống \(E_{i}\) và \(2\) ống nhánh đi ra từ đó là \(B_{1i}\) và \(B_{2i}\). Đường ống số \(1\) nối với chuồng bò; khoảng cách từ phần cuối của đường ống này tới chuồng bò là \(1\).

Input

Dòng 1: 2 số nguyên cách nhau bởi dấu cách: \(N\) và \(C\)
Dòng \(2...C+1\): Dòng \(i+1\) mô tả nút ống \(i\) với ba số nguyên cách nhau bởi dấu cách: \(E_{i},B_{1i}\), và \(B_{2i}\).

Output

Dòng \(1...N\): Dòng \(i\) chứa \(1\) số nguyên là khoảng cách từ chuồng tới "phần cuối" của ống thứ \(i\).

Constraints

\(3 \leq N \leq 99999\), \(N\) lẻ
\(1 \leq C \leq N\)
\(1 \leq E_{i} \leq N\)
\(2 \leq B_{1i}, B_{2i} \leq N\)

Example

Test 1

Input

5 2
3 5 4
1 2 3

Output

Note

Dữ liệu ở trên mô tả bản đồ ống nước sau:
+-––––––-+
| Chuồng |
+-––––––-+
| 1
*
2 / \ 3
*
4 / \ 5
Ống 1 luôn cách chuồng 1 đoạn là 1. Ống 2 và 3 nối với ống 1 nên khoảng cách sẽ là 2. Ống 4 và 5 nối với ống 3 nên khoảng cách sẽ là 3.
```

2. 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\)

3. CSES - Company Queries I | Truy vấn công ty I

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

Một công ty có \(n\) nhân viên, tạo thành một hệ thống phân cấp dạng cây trong đó mỗi nhân viên, ngoại trừ tổng giám đốc đều có một ông chủ.

Nhiệm vụ của bạn là xử lý \(q\) truy vấn dưới dạng: ai là người sếp cao hơn nhân viên \(x\) \(k\) bậc trong hệ thống phân cấp?

Input

Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(q\): số lượng nhân viên và truy vấn. Các nhân viên được đánh số \(1,2,\ldots,n\) và người số \(1\) là tổng giám đốc.
Dòng tiếp theo có \(n-1\) số nguyên \(e_2,e_3,\ldots,e_n\): người chủ mỗi nhân viên \(2,3,\ldots,n\).
Cuối cùng, có \(q\) dòng mô tả các truy vấn. Mỗi dòng có hai số nguyên \(x\) và \(k\) ứng với câu hỏi: "Ai là người sếp cao hơn nhân viên \(x\) \(k\) bậc?"

Output

In câu trả lời cho mỗi truy vấn. Nếu không tồn tại một ông chủ như vậy, hãy in -1.

Constraints

\(1 \leq n,q \leq 2\cdot10^5\)
\(1 \leq e_i \leq i-1\)
\(1 \leq x \leq n\)
\(1 \leq k \leq n\)

Example

Test 1

Input

Output

3
1
-1

4. CSES - Subordinates | Cấp dưới

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

Cho biết cấu trúc của một công ty, nhiệm vụ của bạn là tính số lượng cấp dưới của mỗi người.

Input

Dòng đầu tiên chứa một số nguyên \(n\) \((1 \leq n \leq 2 \times 10^5)\): số lượng nhân viên. Các nhân viên được đánh số \(1, 2, \ldots, n,\) và người có số \(1\) là tổng giám đốc của công ty.
Sau đó là \(n-1\) số nguyên: cấp trên trực tiếp trong công ty của mỗi nhân viên \(2, 3, \ldots, n\).

Output

In ra \(n\) số nguyên: số lượng cấp dưới của mỗi người \(1, 2, \ldots, n\).

Example

Test 1

Input

5
1 1 2 3

Output

4 1 1 0 0

5. CSES - Counting Paths | Đếm đường đi

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

Cho một cây có \(n\) nút, các nút trên cây được đánh số lần lượt là \(1,2,3,...,n\) và \(m\) con đường.

Nhiệm vụ của bạn là với mỗi nút, hãy đếm số đường đi chứa nút này.

Input

Dòng đầu tiên chứa 2 số \(n\) và \(m\)
\(n - 1\) dòng tiếp theo, mỗi dòng chứa chứa 2 số \(a\) và \(b\), thể hiện rằng có một cạnh nối hai nút \(a\) và \(b\)
\(m\) dòng cuối, mỗi dòng chứa 2 số \(a\) và \(b\), thể hiện rằng có một con đường từ nút \(a\) tới \(b\)

Constraints

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

Output

In ra \(n\) số: số lượng đường đi qua mỗi nút \(1,2,3,\dots,n\)

Example

Test 1

Input

Output

3 1 3 1 1