Bài tập

Cho một cây có gốc gồm \(n\) nút. Các nút được đánh số từ \(1\) đến \(n\), và nút \(1\) là gốc của cây. Mỗi nút có một giá trị.

Bạn cần xử lý hai loại truy vấn sau:

• Cập nhật giá trị của một nút: Thay đổi giá trị của nút \(s\) thành \(x\).
• Tính tổng: Tính tổng giá trị của tất cả các nút trên đường đi từ gốc cây (nút \(1\)) đến nút \(s\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 2 \cdot 10^5\)), lần lượt là số lượng nút và số lượng truy vấn.
• Dòng thứ hai chứa \(n\) số nguyên \(v_1, v_2, \ldots, v_n\) (\(1 \le v_i \le 10^9\)), là giá trị ban đầu của các nút.
• \(n-1\) dòng tiếp theo mô tả các cạnh của cây. Mỗi dòng chứa hai số nguyên \(a\) và \(b\) (\(1 \le a, b \le n\)), cho biết có một cạnh nối giữa hai nút \(a\) và \(b\).

• Cuối cùng là \(q\) dòng mô tả các truy vấn. Mỗi truy vấn có dạng:

• "1 s x": Thay đổi giá trị của nút \(s\) thành \(x\) (\(1 \le s \le n, 1 \le x \le 10^9\)).

• "2 s": Tính tổng giá trị trên đường đi từ gốc đến nút \(s\) (\(1 \le s \le n\)).

Output

• Với mỗi truy vấn loại 2, in ra tổng giá trị tính được trên một dòng.

Example

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

9
9

Scoring

• Subtask 1 (30 điểm): \(n, q \le 1000\).
• Subtask 2 (70 điểm): Không có ràng buộc gì thêm.

Lục địa QT có tổng cộng \(N\) đất nước (được đánh số từ \(1\) đến \(N\)) và có \(M\) con đường hai chiều nối giữa các đất nước với nhau. Đất nước RoNE có chỉ số là \(1\), và đất nước NhaNTH có chỉ số là \(N\). Quân đội của đất nước RoNE có \(X\) quân lính và đang muốn xuất quân đi đánh chiếm đất nước thực dân NhaNTH.

Ở mỗi đất nước trên lục địa QT đều có quân thực dân của đất nước NhaNTH chiếm đóng (kể cả đất nước của RoNE), đất nước thứ \(i\) có \(A_i\) quân thực dân. Khi đội quân của RoNE đi qua một đất nước, sẽ có một trận chiến xảy ra. Nếu số lượng quân của RoNE nhiều hơn số lượng quân thực dân tại đất nước đó, quân đội RoNE sẽ toàn thắng, chiếm được đất nước đó và không có thiệt hại nào. Ngược lại, đội quân RoNE vẫn sẽ chiến thắng và chiếm được đất nước đó nhưng số lượng quân sống sót chỉ còn một nửa (nếu số lượng quân lính của RoNE là \(x\) thì sẽ chỉ còn lại \(\lfloor \frac{x}{2}\rfloor\)). Đội quân RoNE cần phải bắt đầu từ đất nước của mình đến đất nước NhaNTH và tiêu diệt tất cả quân thực dân trên đường đi.

Nếu bạn là quân sư của đất nước RoNE, hãy tìm một đường hành quân tốt nhất sao cho có thể bảo toàn được nhiều quân lính nhất có thể sau khi chiếm được đất nước NhaNTH.

Input

• Dòng đầu tiên gồm \(2\) số \(N,M\) là số lượng đất nước và số lượng đường đi giữa các đất nước.
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u,v\) mô tả một con đường nối giữa hai đất nước \(u\) và \(v\).
• Dòng tiếp theo chứa số nguyên \(X\ (1\le X\le10^9)\) là số lượng quân lính của đất nước RoNE.
• Dòng tiếp theo chứa \(N\) số nguyên dương mô tả dãy \(A\ (1\le A_i\le10^9)\) là số lượng quân thực dân tại mỗi đất nước.

Output

• Ghi ra số lượng quân lính tối đa có thể sống sót sau khi chiếm được đất nước NhaNTH. Nếu không thể chiếm đánh thành công, ghi ra \(0\).

Example

4 4
1 2
1 3
2 4
3 4
7
10 2 3 1

3

4 4
1 2
1 3
2 4
3 4
7
10 3 3 1

0

Scoring

• Subtask \(1\) (\(20\%\) số điểm) \(1 \le N,M \le 1000\).
• Subtask \(2\) (\(30\%\) số điểm) \(1 \le N,M \le 100000\).
• Subtask \(3\) (\(50\%\) số điểm) \(1 \le N, M \le 500000\).

Khu Trang ở có \(N\) ngôi nhà đánh số từ \(1\) đến \(N\), các ngôi nhà được nối với nhau bởi các con đường. Từ một ngôi nhà bất kỳ sang một ngôi nhà khác luôn có một và chỉ một con đường một chiều, độ dài các con đường có thể không giống nhau. Nhà Trang là ngôi nhà số \(1\). Một ngày nọ, Trang nhận được đơn đặt hàng của \(K\) ngôi nhà khác, Trang cần tìm ra lộ trình, xuất phát từ nhà, đi tới các ngôi nhà để giao hàng, và quay trở về nhà; sao cho tổng độ dài đường đi là nhỏ nhất.

Do điều kiện khó khăn, Trang chỉ mua được Ipod, Itouch, Iphone, Ipad, Iwatch mà chưa đủ tiền mua MacBook. Vì vậy, Trang cần sự giúp đỡ của các bạn để tìm ra độ dài đường đi ngắn nhất. Các bạn hãy giúp Trang nhé!

Input

Dòng đầu tiên chứa số nguyên \(N\) là số ngôi nhà, và số nguyên \(K\) là số ngôi nhà có đơn đặt hàng. \((2 ≤ N ≤500,1 ≤ K < N)\)

\(N\) dòng tiếp theo, mỗi dòng gồm \(N\) số nguyên. Số thứ \(j\) trong dòng thứ \(i\) (ký hiệu \(c_{i, j}\)) là độ dài đường đi từ ngôi nhà \(i\) tới ngôi nhà \(j\). \((0 ≤ c_{i,j} ≤ 10^8\), \(c_{i,i} = 0\)).

Dòng cuối cùng chứa \(K\) số nguyên phân biệt là \(K\) ngôi nhà có đơn đặt hàng. Ngôi nhà số \(1\)
không có đơn đặt hàng.

Output

In ra một số nguyên duy nhất là độ dài lộ trình nhỏ nhất tìm được.

Example

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

28

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