Bài tập

Cho một cây có gốc có \(n\) đỉnh. Mỗi đỉnh có một mã định danh \(id\) và một trọng số \(w(id)\). Gốc của cây có định danh là \(r\). Có \(Q\) thao tác dạng:

• \(0\) \(p\) \(id\) \(w\): Thêm một đỉnh mới với định danh \(id\), trọng số \(w\) và nhận \(p\) làm nút cha;

• \(1\) \(id\) \(a\): Tìm \(min(a ∧ w)\) và \(max(a ∧ w)\) với \(w\) là trọng số của một đỉnh nào đó trên đường đi đơn từ \(id\) đến \(r\).

Input

• Dòng đầu ghi số đỉnh ban đầu và số thao tác: \(n\) \(Q\);

• Dòng thứ hai mô tả đỉnh gốc: \(r\) \(w(r)\);

• \(n − 1\) dòng tiếp theo, mỗi dòng mô tả một đỉnh của cây: \(id\) \(p\) \(w(id)\) là định danh, định danh của đỉnh cha, trọng số;

• \(Q\) dòng tiếp theo, mỗi dòng mô tả một thao tác, gồm \(3\) hoặc \(4\) số nguyên đã được mã hóa. Để giải mã, số \(s\) sẽ được thay bằng \(s ∧ premin ∧ premax\). Ở đây \(premin\), \(premax\) là kết quả trước đó hoặc \(0\) \(0\) nếu chưa có thao tác loại \(1\) nào.

Các định danh được đảm bảo khác nhau nhưng không nhất thiết tạo thành hoán vị của \([n]\). Dữ liệu đảm bảo hợp lệ.

Output

Với mỗi thao tác loại \(1\), in ra hai số trên một dòng.

Example

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

2 5
0 7

Scoring

• \(1 ≤ n, Q ≤ 10^5\); \(1 ≤ id, w, a < 2^{31}\);

• \(50\%\) số test có \(1 ≤ n, Q ≤ 5000\).

Cho một cây có trọng số gồm \(n\) đỉnh. Cây là một đồ thị vô hướng liên thông không có chu trình.

Có \(m\) truy vấn, truy vấn thứ \(i\) là một số nguyên dương \(q_{i}\). Mỗi truy vấn bạn cần trả lời có bao nhiêu cặp \((u, v) (u < v)\) mà cạnh có trọng số lớn nhất trên đường đi từ đỉnh \(u\) đến đỉnh \(v\) có giá trị không vượt quá \(q_{i}\).

Input

Dòng đầu tiên gồm hai số nguyên dương \(n, m\) - số lượng đỉnh và số lượng truy vấn.

\(n - 1\) dòng tiếp theo, mỗi dòng gồm \(3\) số \(x, y, w\) - có cạnh nối đỉnh x và đỉnh y, cạnh đó có trọng số là \(w\). \((x, y <= n, w <= 10^9)\)

Dòng cuối cùng gồm \(m\) số nguyên dương \(q_{1}, q_{2}, ... , q_{m}\). \((q_{i} <= 10^9)\)

Output

Gồm \(m\) số, mỗi số cách nhau một dấu cách, là kết quả của các truy vấn.

Example

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

21 7 15 21 3 

1 2
1 2

0 0 

3 3
1 2 1
2 3 2
1 3 2

1 3 3 

Scoring

Có \(25\) phần trăm số test có \(n, m <= 20\)

Có \(25\) phần trăm số test có \(n, m <= 500\)

Có \(50\) phần trăm số test có \(n, m <= 2.10^5\)

Có thể nhận thấy ở thời điểm hiện tại, ngành công nghiệp game Esport ngày càng phát triển. Khi nói đến tựa game Esport nổi tiếng và hấp dẫn nhất, không thể thiếu Liên Minh Huyền Thoại (League of Legends). Với mức độ phủ sóng khủng khiếp trên toàn cầu nên các giải đấu về trò chơi này luôn nhận được sự quan tâm của đông đảo người hâm mộ. Và giải đấu LCK cũng là một trong số đó.

LCK là viết tắt của League of Legends Champions Korea, trước đây được biết đến với tên Ongamenet LCK (OGN) và được tổ chức bởi 1Ongamenet, là đấu trường cao nhất của bộ môn thể thao điện tử Liên Minh Huyền Thoại tại Hàn Quốc". Hiện tại, LCK mùa hè \(2023\) đã chính thức khép lại với chiến thắng không thể bàn cãi của GenG.

Fekar - một trong những tuyển thủ huyền thoại của làng Liên Minh Huyền Thoại, sau một thời gian dài gắn bó đã giải nghệ. Fekar đã được đề cử lên làm trưởng ban tổ chức của giải đấu LCK. Vì một lí do nào đó, Fekar đã thay đổi cơ cấu của giải đấu này như sau:

Trước khi bắt đầu mùa giải, mỗi tuyển thủ đều sẽ có một huy hiệu hiển thị một số nguyên \(h_{i}\) - đại diện cho chỉ số kĩ năng của tuyển thủ đó (với \(i\) là số hiệu của tuyển thủ, có tất cả \(n\) tuyển thủ tham gia thi đấu). Thay vì thi đấu theo đội tuyển của mình với hình thức \(5\) vs \(5\), Fekar đã thay đổi luật, tất cả các tuyển thủ sẽ không theo một đội tuyển nào, xếp các tuyển thủ từ trái sang phải theo thứ tự từ \(1\) đến \(n\), sau đó sẽ chia lại các đội tuyển thi đấu (đồng nghĩa rằng bạn sẽ không biết đồng đội của bạn là ai). Fekar yêu cầu các tuyển thủ thuộc cùng một đội tuyển phải đứng sát nhau, một tuyển thủ phải thuộc chính xác một đội tuyển. Nói cách khác, một đội tuyển thi đấu sẽ là một đoạn con trên dãy các tuyển thủ. Quy định này sẽ không hạn chế người của một đội tuyển.

Fekar quy định sức mạnh của một đội tuyển là sự chênh lệnh giữa tuyển thủ có chỉ số kĩ năng cao nhất và tuyển thủ có chỉ số kĩ năng thấp nhất. Nói một cách "công thức" hơn,
nếu tuyển thủ đầu tiên của đội tuyển \(X\) có số thứ tự là \(i\), và tuyển thủ cuối cùng có số thứ tự là \(j\) \((1 \leq i \leq j \leq n)\), sức mạnh đội tuyển là giá trị \(max(h_{i}...h_{j}) - min(h_{i}...h_{j})\).

Gọi sức mạnh tổng thể của giải đấu là tổng sức mạnh của các đội tuyển, Fekar muốn giá trị này đạt càng lớn càng tốt, các bạn hãy giúp Fekar chia đội tuyển một cách hợp lí nhé!

Input

Dòng đầu tiên là số nguyên \(n\) - số tuyển thủ thi đấu \((2 \leq n \leq 10^6)\).

Dòng tiếp theo là \(n\) số nguyên \(h_{1}, h_{2}, h_{3}, ..., h_{n}\) \((-10^9 \leq h_{i} \leq 10^9)\).

Output

Kết quả bài toán.

Example

5
1 2 3 1 2

3

Scoring

\(20\%\) số test tương ứng với \(20\%\) số điểm có \(n \leq 20\).

\(20\%\) số test tương ứng với \(20\%\) số điểm, \(h_{i} <= h_{i + 1}\) \((1 \leq i < n)\).

\(20\%\) số test tương ứng với \(20\%\) số điểm có \(n \leq 5000\).

\(20\%\) số test tương ứng với \(20\%\) số test, \(h_{i} = a\) hoặc \(h_{i} = b\) với \(a, b\) là hằng số.

\(20\%\) số test còn lại không có ràng buộc gì thêm.

Tại trung tâm lưu trữ dữ liệu quốc gia của quốc gia LQD, giáo sư Q vừa khánh thành một hệ thống vận chuyển tài liệu tự động sử dụng các robot điện siêu nhỏ mang tên Alset. Để tối ưu hóa quy trình, các nhà đầu tư cần mô phỏng khả năng di chuyển của robot giữa các kho lưu trữ.

Hệ thống kho lưu trữ được đơn giản hóa thành một lưới ô vuông vô tận trên hệ trục tọa độ \(Oxy\). Tại mỗi điểm có tọa độ nguyên \((x, y)\) đều có một điểm giao nhận tài liệu. Các con đường vận chuyển chỉ chạy dọc theo các trục tọa độ, nối các điểm \((x, y)\) với \((x, y+1)\) và \((x+1, y)\).

Robot Alset di chuyển từ một điểm giao nhận này sang một điểm giao nhận liền kề mất đúng \(1\) đơn vị năng lượng (tương ứng với khoảng cách Manhattan là \(1\)). Cụ thể, xe tiêu tốn \(|x-u| + |y-v|\) đơn vị năng lượng để đi giữa hai điểm \((x, y)\) và \((u, v)\).

Trung tâm có \(n\) trạm nạp năng lượng đặc biệt, trạm thứ \(i\) được đặt tại tọa độ \((x_i, y_i)\). Mỗi khi dừng tại một trạm nạp, robot sẽ được sạc đầy năng lượng lên mức \(w\) (với \(w\) là dung lượng tối đa của pin). Một robot chỉ có thể di chuyển giữa hai điểm nếu năng lượng cần thiết không vượt quá dung lượng pin hiện có. Trong quá trình di chuyển từ trạm \(s\) đến trạm \(t\), robot có thể ghé thăm bất kỳ trạm sạc nào khác trên đường đi để nạp lại năng lượng.

Hệ thống cần xử lý \(q\) yêu cầu mô phỏng. Với mỗi yêu cầu thứ \(j\), bạn cần xác định dung lượng pin tối thiểu \(w\) mà robot cần có để có thể di chuyển thành công từ trạm sạc \(s_j\) đến trạm sạc \(t_j\).

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 2 \cdot 10^5\)) --- số lượng trạm sạc và số lượng yêu cầu mô phỏng.

Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(x_i\) và \(y_i\) (\(|x_i|, |y_i| \le 10^9\)) --- tọa độ của trạm sạc thứ \(i\).

Trong \(q\) dòng tiếp theo, dòng thứ \(j\) chứa hai số nguyên \(s_j\) và \(t_j\) (\(1 \le s_j, t_j \le n\)) --- chỉ số của trạm bắt đầu và trạm kết thúc trong yêu cầu thứ \(j\).

Output

In ra \(q\) dòng, mỗi dòng chứa một số nguyên duy nhất là dung lượng pin tối thiểu \(w\) tìm được cho yêu cầu tương ứng.

Example

5 3
0 0
0 0
3 3
1 2
6 8
1 2
2 3
1 5

0
3
8

Scoring

• Subtask 1 (20% số điểm): \(n, q \le 100\).
• Subtask 2 (20% số điểm): \(n, q \le 1000\).
• Subtask 3 (20% số điểm): Tất cả các trạm sạc nằm trên trục tung (\(x_i = 0\)).
• Subtask 4 (20% số điểm): Các trạm sạc chỉ nằm trên hai đường thẳng dọc sát nhau (\(0 \le x_i \le 1\)).
• Subtask 5 (20% số điểm): Không có ràng buộc gì thêm.