📘 Mô tả

Cho một cây gồm n đỉnh được đánh số từ 1 đến n. Gốc của cây là đỉnh số 1. Bạn sẽ nhận được q truy vấn, mỗi truy vấn gồm hai đỉnh u và v, yêu cầu bạn tìm tổ tiên chung gần nhất (LCA) của hai đỉnh này trong cây.

📥 Input

• Dòng đầu tiên chứa số nguyên n (2 ≤ n ≤ 10⁵): số đỉnh của cây.
• n - 1 dòng tiếp theo, mỗi dòng chứa hai số nguyên x và y: thể hiện cạnh nối giữa đỉnh x và đỉnh y.
• Dòng tiếp theo chứa số nguyên q (1 ≤ q ≤ 10⁵): số lượng truy vấn.
• q dòng tiếp theo, mỗi dòng chứa hai số nguyên u và v: truy vấn tìm tổ tiên chung gần nhất của u và v.

📤 Output

In ra q dòng, mỗi dòng là một số nguyên — tổ tiên chung gần nhất của u và v trong cây.

🧪 Ví dụ

Input:

5
1 2
1 3
2 4
2 5
3
4 5
4 3
2 3

Output:

2
1
1

📎 Ghi chú

• Truy vấn 1: LCA(4, 5) = 2.
• Truy vấn 2: LCA(4, 3) = 1.
• Truy vấn 3: LCA(2, 3) = 1.

📘 Mô tả

Có N con bò (1 ≤ N ≤ 10^5), để thuận tiện ta đánh số từ 1 → N, đang ăn cỏ trên N đồng cỏ, để thuận tiện ta cũng đánh số các đồng cỏ từ 1 → N. Biết rằng con bò i đang ăn cỏ trên đồng cỏ i.

Một vài cặp đồng cỏ được nối với nhau bởi 1 trong N - 1 con đường 2 chiều mà các con bò có thể đi qua. Con đường i nối 2 đồng cỏ Ai và Bi (1 ≤ Ai, Bi ≤ N) với độ dài là Li (1 ≤ Li ≤ 10000).

Các con đường được thiết kế sao cho với 2 đồng cỏ bất kỳ đều có duy nhất 1 đường đi giữa chúng. Như vậy các con đường này đã hình thành 1 cấu trúc cây.

Các chú bò rất có tinh thần tập thể và muốn được thăm thú thường xuyên. Vì vậy lũ bò muốn bạn giúp chúng tính toán độ dài đường đi giữa Q (1 ≤ Q ≤ 1000) cặp đồng cỏ (mỗi cặp được mô tả là 2 số nguyên p1, p2 (1 ≤ p1, p2 ≤ N)).

📥 Input

• Dòng 1: 2 số nguyên cách nhau bởi dấu cách: N và Q
• Dòng 2 đến N: Dòng i + 1 chứa 3 số nguyên cách nhau bởi dấu cách: Ai, Bi, Li
• Dòng N + 1 đến N + Q: Mỗi dòng chứa 2 số nguyên khác nhau cách nhau bởi dấu cách mô tả 1 yêu cầu tính toán độ dài đường đi giữa 2 đồng cỏ mà lũ bò muốn đi thăm qua lại p1 và p2.

📤 Output

In ra Q dòng, mỗi dòng là độ dài đường đi giữa 2 đồng cỏ tương ứng với yêu cầu thứ i.

🧪 Ví dụ

Input:

4 2
2 1 2
4 3 2
3 2 4
1 2
3 1

Output:

2
6

📘 Mô tả

Cho một cây gồm n đỉnh được đánh số từ 1 đến n. Cây không định hướng và không có chu trình. Bạn sẽ nhận được q truy vấn. Mỗi truy vấn gồm ba số nguyên r, u, v, yêu cầu bạn tìm tổ tiên chung gần nhất của u và v trong cây khi gốc là đỉnh r.

📥 Input

• Dòng đầu tiên chứa số nguyên n (2 ≤ n ≤ 10⁵): số đỉnh của cây.
• n - 1 dòng tiếp theo, mỗi dòng chứa hai số nguyên x và y: thể hiện cạnh nối giữa đỉnh x và y.
• Dòng tiếp theo chứa số nguyên q (1 ≤ q ≤ 10⁵): số lượng truy vấn.
• q dòng tiếp theo, mỗi dòng chứa ba số nguyên r, u, v: truy vấn tìm tổ tiên chung gần nhất của u và v trong cây khi gốc là r.

📤 Output

In ra q dòng, mỗi dòng là một số nguyên — tổ tiên chung gần nhất của u và v trong cây khi gốc là r.

🧪 Ví dụ

Input:

5
1 2
1 3
2 4
2 5
3
1 4 5
2 4 3
4 5 3

Output:

2
2
2

📘 Mô tả

Ban đầu cây chỉ có một đỉnh gốc là đỉnh số 1. Sau đó có q truy vấn. Có hai loại truy vấn:

• 1 u: thêm một đỉnh mới, đánh số tự động tiếp theo, làm con trực tiếp của đỉnh u.
• 2 u v: in ra tổ tiên chung gần nhất (LCA) của hai đỉnh u và v trong cây hiện tại.

📥 Input

• Dòng đầu tiên chứa số nguyên q (1 ≤ q ≤ 10⁵): số lượng truy vấn.
• q dòng tiếp theo, mỗi dòng là một truy vấn có dạng 1 u hoặc 2 u v như mô tả ở trên.

📤 Output

Với mỗi truy vấn loại 2, in ra một dòng chứa số nguyên duy nhất là tổ tiên chung gần nhất của u và v.

🧪 Ví dụ

Input:

6
1 1
1 1
1 2
2 2 3
2 4 3
2 4 1

Output:

1
1
1

📘 Mô tả

Ở một vùng đồi núi, có n ngôi làng được nối với nhau bằng những con đường tạo thành một cây (giữa hai làng bất kỳ luôn có đúng một đường đi duy nhất).

Mỗi ngày, Trường và Lực đều đi từ một làng này sang một làng khác để thăm bạn bè. Cụ thể, có q kế hoạch đi chơi, mỗi kế hoạch gồm bốn ngôi làng u, v, x, y tương ứng với hành trình của Trường (từ u đến v) và Lực (từ x đến y).

Nhiệm vụ của bạn là xác định đoạn đường chung mà cả Trường và Lực đều đi qua trong ngày hôm đó. Nếu có, hãy in ra hai đầu mút a và b của đoạn đường giao nhau sao cho a ≤ b. Nếu không có đoạn nào trùng, in ra -1.

📥 Input

• Dòng đầu tiên chứa hai số nguyên n và q (2 ≤ n ≤ 10⁵, 1 ≤ q ≤ 10⁵): số làng và số kế hoạch đi chơi.
• n - 1 dòng tiếp theo, mỗi dòng chứa hai số nguyên x và y: con đường nối hai ngôi làng.
• q dòng tiếp theo, mỗi dòng gồm bốn số nguyên u, v, x, y: mô tả hành trình của Trường và Lực.

📤 Output

Với mỗi kế hoạch, in ra hai số nguyên a và b đại diện cho đoạn đường chung giữa hành trình của Trường và Lực (thỏa a ≤ b), hoặc in -1 nếu không có đoạn nào chung.

🧪 Ví dụ

Input:

5 2
1 2
1 3
2 4
2 5
4 5 3 5
4 5 3 1

Output:

2 5 
-1

📘 Mô tả

Cho một cây gồm n đỉnh, đánh số từ 1 đến n. Mỗi đỉnh i có trọng số là wi.

Bạn cần tính tổng trọng số của các đỉnh trong cây con gốc tại mỗi đỉnh u, tức là tổng trọng số của u và tất cả các đỉnh nằm trong cây con có gốc là u.

📥 Input

• Dòng đầu tiên là số nguyên n (1 ≤ n ≤ 10⁵): số đỉnh của cây.
• Dòng thứ hai gồm n số nguyên w1, w2, ..., wn (1 ≤ wi ≤ 10⁴): trọng số của từng đỉnh.
• n - 1 dòng tiếp theo, mỗi dòng gồm hai số nguyên u và v (1 ≤ u, v ≤ n): biểu thị một cạnh nối giữa hai đỉnh u và v.

📤 Output

In ra n số nguyên, số thứ i là tổng trọng số của cây con gốc tại đỉnh i.

🧪 Ví dụ

Input:

5
1 2 3 4 5
1 2
1 3
3 4
3 5

Output:

15 2 12 4 5

📎 Ghi chú

• Cây có gốc tại đỉnh 1 bao gồm tất cả các đỉnh, tổng trọng số là 15.
• Cây con gốc tại đỉnh 2 chỉ có chính nó nên tổng là 2.
• Cây con gốc tại đỉnh 3 gồm các đỉnh 3, 4, 5 nên tổng là 3 + 4 + 5 = 12.

Mô tả

Trong một khu vườn thần kỳ mọc lên một cổ thụ có n cành, gốc đặt tại cành 1. Mỗi cành được xem như một nhánh con; ban đầu trên mọi cành đều chưa có quả (giá trị 0). Người làm vườn có hai hành động:

• 1 u v - Rải "phân bón" lên cành u; mọi nhánh bên dưới cành đó lập tức ra thêm v quả (có thể âm nếu sâu bệnh làm mất quả).
• 2 u - Hỏi cành u hiện đang có bao nhiêu quả.

Hãy giúp người làm vườn xử lý q hành động và trả lời các câu hỏi loại 2.

Input

• Dòng đầu chứa hai số nguyên n, q (1 ≤ n,q ≤ 105).
• n - 1 dòng tiếp, mỗi dòng gồm hai số u, v - hai cành kề nhau.
• q dòng tiếp, mỗi dòng là:
    • 1 u v - rải phân bón
    • 2 u - truy vấn số quả

Output

Với mỗi truy vấn loại 2, in ra số nguyên duy nhất là lượng quả trên cành được hỏi.

Ràng buộc

• 1 ≤ n,q ≤ 105
• 1 ≤ u ≤ n
• |v| ≤ 109

Ví dụ

Input

3 5
1 2
1 3
1 1 5
2 2
1 3 1
2 3
2 1

Output

5
6
5

📘 Câu chuyện

Trên thân cây cổ thụ có n chiếc lá đánh số từ 1 đến n, nối với nhau thành một mạng lưới không chu trình (một cây). Mỗi lá i ẩn chứa một giọt mật có độ ngon ai. Chú sâu nhỏ thích phiêu lưu:

• Loại 1 (1 u v): chú xuất phát tại lá u, bò dọc thân cây đến lá v và liếm trọn mật của mọi lá trên hành trình. Bọn trẻ muốn biết tổng độ ngon mà chú sâu thưởng thức.
• Loại 2 (2 x w): bọn trẻ rót thêm mật vào lá x, thay đổi độ ngon của lá đó thành w.

📥 Input

• Dòng đầu chứa hai số nguyên n và q (1 <= n, q <= 10^5).
• Dòng thứ hai chứa n số nguyên a1, a2, …, an (1 <= ai <= 10^9).
• n - 1 dòng tiếp theo, mỗi dòng ghi hai số u, v (1 <= u, v <= n) — mô tả một cành cây nối hai lá.
• q dòng cuối, mỗi dòng mô tả một truy vấn:
  • 1 u v — truy vấn loại 1.
  • 2 x w — truy vấn loại 2.

📤 Output

Với mỗi truy vấn loại 1, in ra trên một dòng duy nhất tổng độ ngon của các lá trên đường đi duy nhất từ u tới v. Với truy vấn loại 2, không in gì.

🧪 Ví dụ

Input

5 5
3 2 5 4 1
1 2
1 3
2 4
2 5
1 4 5
2 2 10
1 4 5
1 3 4
1 2 3

Output

7
15
22
18

📎 Giải thích

• Ban đầu, đường 4 → 5 đi qua lá 4, 2, 5: 4 + 2 + 1 = 7.
• Cập nhật lá 2 thành 10.
• Đường 4 → 5 lúc này: 4 + 10 + 1 = 15.
• Đường 3 → 4: lá 3, 1, 2, 4: 5 + 3 + 10 + 4 = 22.
• Đường 2 → 3: lá 2, 1, 3: 10 + 3 + 5 = 18.

📎 Hint

• Mình đã nói dùng euler tour thuần thì không được nhưng +lca thì không thành vấn đề. Hãy tìm cách triệt tiêu các cành không cần thiết trên euler tour và bù trừ.

📘 Mô tả

Một cái cây có n đỉnh được đánh số từ 1 đến n, mỗi đỉnh i mang giá trị ban đầu ai gọi là độ ngon. Có q truy vấn được thực hiện trên cây.

Có hai loại truy vấn:

• 1 u v: hỏi tổng độ ngon trên đường đi giữa hai đỉnh u và v trên cây.
• 2 u k: cộng thêm k vào tất cả các đỉnh thuộc cây con gốc tại đỉnh u.

📥 Input

• Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 105) — số đỉnh của cây.
• Dòng thứ hai chứa n số nguyên a1, a2, ..., an (1 ≤ ai ≤ 109).
• n - 1 dòng tiếp theo, mỗi dòng gồm hai số nguyên u, v mô tả một cạnh nối hai đỉnh.
• Dòng tiếp theo chứa số nguyên q — số lượng truy vấn.
• q dòng cuối, mỗi dòng chứa một trong hai loại truy vấn đã nêu.

📤 Output

Với mỗi truy vấn loại 1, in ra tổng độ ngon trên đường đi từ u tới v.

🧪 Ví dụ

Input:

5
3 2 5 4 1
1 2
1 3
2 4
2 5
4
1 4 5
2 2 1
1 3 4
1 2 3

Output:

7
16
11

📎 Ghi chú

• Truy vấn đầu tiên: đường đi từ 4 → 2 → 5: tổng = 4 + 2 + 1 = 7.
• Truy vấn thứ hai: tăng giá trị tất cả các đỉnh trong cây con tại đỉnh 2 lên 1 → đỉnh 2, 4, 5 đều tăng thêm 1.
• Truy vấn tiếp theo: đường đi từ 3 → 1 → 2 → 4: tổng = 5 + 3 + 3 + 4 = 15.
• Truy vấn cuối: đường đi từ 2 → 1 → 3: tổng = 3 + 3 + 4 = 10.

📘 Mô tả

Cho một cây có gốc gồm n đỉnh, gốc là đỉnh 1. Mỗi đỉnh mang một màu. Với mỗi đỉnh hãy xác định số màu khác nhau xuất hiện trong toàn bộ cây con của đỉnh đó.

📥 Input

• Dòng đầu chứa một số nguyên n (1 ≤ n ≤ 2·105) — số đỉnh của cây.
• Dòng thứ hai chứa n số nguyên c1, c2, …, cn (1 ≤ ci ≤ 109) — màu của từng đỉnh.
• n - 1 dòng tiếp theo, mỗi dòng gồm hai số nguyên a và b (1 ≤ a, b ≤ n) — mô tả một cạnh nối giữa a và b.

📤 Output

In ra n số, số thứ i là lượng màu khác nhau trong cây con gốc tại đỉnh i. Các số được in trên một dòng, cách nhau bởi một khoảng trắng.

🧪 Ví dụ

Input:

5
2 3 2 2 1
1 2
1 3
3 4
3 5

Output:

3 1 2 1 1

📎 Ghi chú

• Ở ví dụ trên, cây con của đỉnh 3 gồm các đỉnh 3, 4, 5 có màu 2, 2, 1 nên có 2 màu khác nhau.