Cho một cây gồm ~n~ đỉnh, gốc tại đỉnh ~1~.

Có ~q~ truy vấn, mỗi truy vấn có dạng ~(u, v)~ — hãy tìm tổ tiên chung gần nhất của ~u~ và ~v~.

Tổ tiên chung gần nhất của ~u~ và ~v~ là đỉnh sâu nhất đồng thời là tổ tiên của cả ~u~ và ~v~ (mỗi đỉnh được coi là tổ tiên của chính nó).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ — có một cạnh nối ~u~ và ~v~.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ — một truy vấn.

Kết quả

In ra ~q~ dòng, dòng thứ ~i~ là đáp án cho truy vấn thứ ~i~.

Ví dụ

Đầu vào:

7 3
1 2
1 3
2 4
2 5
3 6
3 7
4 5
4 6
2 7

Đầu ra:

2
1
1

Giải thích: Đỉnh ~4~ và ~5~ đều là con của ~2~ nên tổ tiên chung gần nhất là ~2~. Với ~(4, 6)~ và ~(2, 7)~, hai đỉnh nằm ở hai nhánh khác nhau của gốc nên đáp án là ~1~.

Giới hạn

• ~1 \le n, q \le 10^5~
• ~1 \le u, v \le n~

Có thể ~u = v~, khi đó đáp án chính là ~u~. Cây có thể sâu tới ~10^5~ nên hãy tránh đệ quy khi duyệt cây.

Cho một cây có trọng số gồm ~n~ đỉnh, gốc tại đỉnh ~1~.

Có ~q~ truy vấn, mỗi truy vấn có dạng ~(u, v)~ — hãy tìm khoảng cách ngắn nhất giữa ~u~ và ~v~.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u~, ~v~, ~w~ — có một cạnh trọng số ~w~ nối ~u~ và ~v~.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ — một truy vấn.

Kết quả

In ra ~q~ dòng, dòng thứ ~i~ là đáp án cho truy vấn thứ ~i~.

Ví dụ

Đầu vào:

7 3
1 2 1
1 3 2
2 4 3
2 5 2
3 6 1
3 7 3
4 5
4 6
2 7

Đầu ra:

5
7
6

Giải thích: Đường đi từ ~4~ đến ~5~ là ~4 \to 2 \to 5~ với chi phí ~3 + 2 = 5~. Đường đi từ ~4~ đến ~6~ là ~4 \to 2 \to 1 \to 3 \to 6~ với chi phí ~3 + 1 + 2 + 1 = 7~.

Giới hạn

• ~1 \le n, q \le 10^5~
• ~1 \le u, v \le n~
• ~1 \le w \le 10^9~

Khoảng cách có thể lên tới ~10^{14}~ nên không vừa trong số nguyên 32 bit. Nếu ~u = v~ thì đáp án là ~0~.

Cho một cây có trọng số gồm ~n~ đỉnh, gốc tại đỉnh ~1~.

Có ~q~ truy vấn, mỗi truy vấn có dạng ~(u, v)~ — hãy tìm trọng số của cạnh nặng nhất trên đường đi đơn giữa ~u~ và ~v~.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u~, ~v~, ~w~ — có một cạnh trọng số ~w~ nối ~u~ và ~v~.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ — một truy vấn.

Kết quả

In ra ~q~ dòng, dòng thứ ~i~ là đáp án cho truy vấn thứ ~i~.

Ví dụ

Đầu vào:

7 3
1 2 1
1 3 2
2 4 3
2 5 2
3 6 1
3 7 3
4 5
2 6
2 1

Đầu ra:

3
2
1

Giải thích: Đường đi ~4 \to 2 \to 5~ có các cạnh trọng số ~3~ và ~2~, nặng nhất là ~3~. Đường đi ~2 \to 1 \to 3 \to 6~ có các cạnh ~1~, ~2~, ~1~, nặng nhất là ~2~. Đường đi ~2 \to 1~ chỉ có một cạnh trọng số ~1~.

Giới hạn

• ~1 \le n, q \le 10^5~
• ~1 \le u, v \le n~
• ~1 \le w \le 10^9~

Nếu ~u = v~ thì đường đi không có cạnh nào, khi đó đáp án là ~0~.

Cho một cây gồm ~n~ đỉnh.

Bạn có một con robot. Bạn có thể đặt nó tại đỉnh ~u~ trên cây và ra lệnh cho nó di chuyển tới đỉnh ~v~ theo đường đi đơn giữa hai đỉnh.

Di chuyển từ đỉnh này sang đỉnh kề tốn ~1~ đơn vị năng lượng. Khi robot hết năng lượng, nó dừng lại.

Có ~q~ truy vấn, mỗi truy vấn có dạng ~(u, v, w)~ — robot xuất phát tại ~u~ và di chuyển về phía ~v~ với ~w~ đơn vị năng lượng ban đầu. Hỏi nó sẽ dừng ở đâu?

Nếu năng lượng đủ để tới ~v~ thì robot dừng tại ~v~.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ — có một cạnh nối ~u~ và ~v~.
• ~q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u~, ~v~, ~w~ — một truy vấn.

Kết quả

In ra ~q~ dòng, dòng thứ ~i~ là đáp án cho truy vấn thứ ~i~.

Ví dụ

Đầu vào:

7 3
1 2
1 3
2 4
2 5
3 6
3 7
1 4 1
5 6 2
6 5 3

Đầu ra:

2
1
2

Giải thích: Truy vấn ~(1, 4, 1)~: đường đi là ~1 \to 2 \to 4~, robot đi được ~1~ bước nên dừng tại ~2~. Truy vấn ~(5, 6, 2)~: đường đi là ~5 \to 2 \to 1 \to 3 \to 6~, đi ~2~ bước nên dừng tại ~1~. Truy vấn ~(6, 5, 3)~: đường đi là ~6 \to 3 \to 1 \to 2 \to 5~, đi ~3~ bước nên dừng tại ~2~.

Giới hạn

• ~1 \le n, q \le 10^5~
• ~1 \le u, v, w \le n~

Nếu ~u = v~ thì robot đã ở đích và dừng ngay tại ~u~.

Cho một cây gồm ~n~ đỉnh, gọi ~d(u, v)~ là số cạnh trên đường đi đơn từ ~u~ đến ~v~. Cho ~q~ truy vấn có dạng ~(a, b, c)~, hãy tìm một đỉnh ~x~ sao cho ~d(a, x) + d(b, x) + d(c, x)~ là nhỏ nhất.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ — có một cạnh nối ~u~ và ~v~.
• ~q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~a~, ~b~, ~c~ — một truy vấn.

Kết quả

Với mỗi truy vấn, in ra đỉnh thỏa mãn điều kiện, mỗi đáp án trên một dòng.

Ví dụ

Đầu vào:

10 7
1 2
1 3
2 4
3 5
2 6
5 7
1 8
4 9
4 10
4 4 2
1 5 8
10 6 9
7 2 5
7 9 2
7 5 4
8 3 4

Đầu ra:

4
1
4
5
2
5
1

Giải thích: Với truy vấn ~(4, 4, 2)~, chọn ~x = 4~ cho tổng ~0 + 0 + 1 = 1~, nhỏ nhất có thể. Với ~(1, 5, 8)~, đỉnh ~1~ nằm trên cả ba đường đi đôi một nên cho tổng nhỏ nhất.

Giới hạn

• ~1 \le n, q \le 10^5~
• ~1 \le a, b, c \le n~

Đỉnh làm cho tổng nhỏ nhất luôn tồn tại và là duy nhất — đó chính là đỉnh nằm trên cả ba đường đi ~a \to b~, ~b \to c~ và ~a \to c~. Các đỉnh ~a~, ~b~, ~c~ không nhất thiết phân biệt.

Cho một cây gồm ~n~ đỉnh, gốc tại đỉnh ~1~. Mỗi đỉnh mang một số, ban đầu bằng ~0~.

Có ~q~ truy vấn, mỗi truy vấn có dạng ~(u, v, w)~ — tăng giá trị của mỗi đỉnh trên đường đi đơn giữa ~u~ và ~v~ thêm ~w~ (tính cả hai đầu mút ~u~ và ~v~).

Hãy tìm giá trị trên mỗi đỉnh sau ~q~ truy vấn.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ — có một cạnh nối ~u~ và ~v~.
• ~q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u~, ~v~, ~w~ — một truy vấn.

Kết quả

In ra ~n~ số nguyên trên một dòng, cách nhau bởi dấu cách — số thứ ~i~ là giá trị trên đỉnh ~i~.

Ví dụ

Đầu vào:

7 3
1 2
1 3
2 4
2 5
3 6
3 7
1 4 1
5 6 2
6 7 5

Đầu ra:

3 3 7 1 2 7 5

Giải thích: Truy vấn đầu tiên cộng ~1~ vào các đỉnh ~1, 2, 4~. Truy vấn thứ hai cộng ~2~ vào các đỉnh ~5, 2, 1, 3, 6~. Truy vấn thứ ba cộng ~5~ vào các đỉnh ~6, 3, 7~. Chẳng hạn đỉnh ~3~ nhận ~2 + 5 = 7~.

Giới hạn

• ~1 \le n, q \le 10^5~
• ~1 \le u, v \le n~
• ~1 \le w \le 10^9~

Nếu ~u = v~ thì chỉ đỉnh đó được cộng thêm ~w~. Giá trị cuối cùng có thể lên tới ~10^{14}~ nên không vừa trong số nguyên 32 bit.

Cho một cây gồm ~n~ đỉnh.

Gọi ~f(u, v)~ là khoảng cách ngắn nhất giữa ~u~ và ~v~ (số cạnh trên đường đi đơn). Cho ~q~ truy vấn, mỗi truy vấn có dạng ~(u, v)~ — hãy đếm số đỉnh ~x~ thỏa mãn ~f(u, x) = f(v, x)~.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ — có một cạnh nối ~u~ và ~v~.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ — một truy vấn.

Kết quả

In ra ~q~ dòng, dòng thứ ~i~ là đáp án cho truy vấn thứ ~i~.

Ví dụ

Đầu vào:

7 3
1 2
1 3
2 4
2 5
3 6
3 7
1 4
5 6
3 7

Đầu ra:

2
1
0

Giải thích: Với ~(1, 4)~, hai đỉnh ~2~ và ~5~ cách đều cả ~1~ và ~4~. Với ~(5, 6)~, chỉ có đỉnh ~1~. Với ~(3, 7)~, khoảng cách giữa hai đỉnh là ~1~ — một số lẻ — nên không có đỉnh nào cách đều cả hai.

Giới hạn

• ~1 \le n, q \le 10^5~
• ~1 \le u, v \le n~

Nếu khoảng cách giữa ~u~ và ~v~ là số lẻ thì đáp án luôn bằng ~0~. Nếu ~u = v~ thì mọi đỉnh đều thỏa mãn, đáp án là ~n~.

Khu dân cư của Oggy được biểu diễn bằng một cây gồm ~n~ ngôi nhà và ~n - 1~ con đường nối chúng. Trong ~q~ ngày, Oggy phải đuổi bắt lũ gián để giữ trật tự khu phố.

Vào ngày thứ ~i~, Oggy xuất phát tại nhà ~u_i~, còn lũ gián ở nhà ~v_i~. Trong mỗi đơn vị thời gian, cả Oggy và lũ gián đều có thể di chuyển sang một ngôi nhà kề hoặc đứng yên tại chỗ (đi qua một con đường mất một đơn vị thời gian).

Với mỗi ngày, hãy xác định số đơn vị thời gian lớn nhất mà Oggy phải bỏ ra để bắt được lũ gián, biết rằng cả hai bên đều di chuyển một cách tối ưu.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~q~.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~u_i~, ~v_i~ — mô tả một con đường.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~u_i~, ~v_i~ — vị trí xuất phát của Oggy và của lũ gián.

Kết quả

In ra ~q~ dòng, mỗi dòng là đáp án cho truy vấn tương ứng.

Ví dụ

Đầu vào:

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

Đầu ra:

4
2
3
3

Giải thích: Ngày đầu tiên Oggy ở nhà ~3~, lũ gián ở nhà ~5~. Lũ gián chạy về nhà ~6~ — chúng tới đó trước Oggy — và Oggy cần ~4~ đơn vị thời gian để đi từ ~3~ tới ~6~.

Giới hạn

• ~1 \le n, q \le 10^5~
• ~1 \le u_i, v_i \le n~

Lũ gián chỉ có thể trú tại những ngôi nhà mà chúng tới được trước Oggy, tức các đỉnh ~x~ thỏa mãn khoảng cách từ ~v~ tới ~x~ nhỏ hơn khoảng cách từ ~u~ tới ~x~. Nếu ~u = v~ thì Oggy bắt được ngay, đáp án là ~0~.

Giống như bất kỳ thủ đô nào, thành phố Skibidi có một hệ thống tàu điện rất phát triển. Hệ thống gồm một số ga được nối với nhau bởi các đường hầm, và giữa hai ga bất kỳ luôn có đúng một đường đi không lặp lại đường hầm nào. Nói cách khác, hệ thống là một cây.

Mỗi ga có một trọng số ~x \in \{-1, 1\}~. Khi Per đi qua một ga có trọng số ~-1~, cậu ấy phải trả ~1~ jack; khi đi qua ga có trọng số ~1~, cậu ấy được thưởng ~1~ jack.

Ban đầu hệ thống chỉ có một ga duy nhất mang số ~1~ với trọng số ~x = 1~. Mỗi ngày xảy ra một trong hai sự kiện:

• Xây ga mới: một ga mới với trọng số ~x~ được nối vào ga ~v~. Ga mới được đánh số lớn hơn số của mọi ga hiện có.
• Truy vấn: cho hai ga ~u~, ~v~ và một số nguyên ~k~. Xét đường đi từ ~u~ tới ~v~, hãy cho biết có tồn tại một đoạn liên tiếp các ga trên đường đi đó mà tổng trọng số đúng bằng ~k~ hay không. Đoạn liên tiếp có thể rỗng, khi đó tổng bằng ~0~.

Nhiệm vụ của bạn là trả lời mọi truy vấn.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên ~t~ — số lượng bộ test.
• Với mỗi bộ test:
  • Dòng đầu chứa một số nguyên ~n~ — số lượng sự kiện.
  • ~n~ dòng tiếp theo, mỗi dòng là một trong hai dạng:
    • + v x — xây một ga mới với trọng số ~x~ nối vào ga ~v~ (ga ~v~ chắc chắn đã tồn tại).
    • ? u v k — một truy vấn trên đường đi giữa hai ga ~u~ và ~v~ (cả hai ga chắc chắn đã tồn tại).

Kết quả

Với mỗi truy vấn, in ra trên một dòng YES nếu tồn tại đoạn liên tiếp có tổng đúng bằng ~k~, ngược lại in ra NO.

Ví dụ

Đầu vào:

1
8
+ 1 -1
? 1 1 2
? 1 2 1
+ 1 1
? 1 3 -1
? 1 1 1
? 1 3 2
? 1 1 0

Đầu ra:

NO
YES
NO
YES
YES
YES

Giải thích: Sau sự kiện đầu tiên, ga ~2~ (trọng số ~-1~) được nối vào ga ~1~.

• Truy vấn ~1~: đường đi chỉ gồm ga ~1~ với trọng số ~1~. Các tổng tạo được là ~0~ và ~1~, không có ~2~.
• Truy vấn ~2~: đường đi ~1 \to 2~ có trọng số ~[1, -1]~. Chọn đoạn chỉ gồm ga ~1~ được tổng ~1~.
• Truy vấn ~3~: đường đi ~1 \to 3~ có trọng số ~[1, 1]~, mọi tổng đều không âm nên không thể bằng ~-1~.
• Truy vấn ~6~: chọn đoạn rỗng, tổng bằng ~0~.

Đầu vào:

1
7
+ 1 -1
+ 2 -1
+ 2 1
+ 3 -1
? 5 2 2
? 3 1 -1
? 5 4 -3

Đầu ra:

NO
YES
YES

Giải thích: Truy vấn cuối xét đường đi ~5 \to 4~ với trọng số ~[-1, -1, -1, 1]~; ba ga đầu cho tổng ~-3~.

Giới hạn

• ~1 \le t \le 10^4~
• ~1 \le n \le 2 \cdot 10^5~
• ~x \in \{-1, 1\}~
• ~-n \le k \le n~
• Tổng các giá trị ~n~ trên tất cả các bộ test không vượt quá ~2 \cdot 10^5~

Điểm mấu chốt: vì mọi trọng số đều là ~\pm 1~, tập các tổng tạo được luôn là một đoạn số nguyên liên tiếp chứa ~0~. Thật vậy, nếu một đoạn có tổng ~S > 0~ thì bỏ đi một ga ở đầu đoạn làm tổng thay đổi đúng ~1~ đơn vị, nên mọi giá trị giữa ~0~ và ~S~ đều đạt được. Tương tự với ~S < 0~.

Do đó đáp án là YES khi và chỉ khi

~\text{minSub}(u, v) \le k \le \text{maxSub}(u, v)~

với ~\text{maxSub}~, ~\text{minSub}~ là tổng đoạn con liên tiếp lớn nhất và nhỏ nhất trên đường đi (cho phép đoạn rỗng, nên ~\text{maxSub} \ge 0 \ge \text{minSub}~).

Việc còn lại là tính hai giá trị đó trên một đường đi bất kỳ của cây đang lớn dần.