Bài tập

Sau chuỗi ngày ôn và thi mệt mỏi, Bờm quyết định du lịch đến đất nước Byteland. Đất nước xinh đẹp này có \(n\) thành phố, các thành phố kết nối với nhau bởi \(n-1\) con đường hai chiều. Con đường thứ \(i\) nối từ thành phố \(x\) đến thành phố \(y\) có độ dài \(w\).

Thêm nữa, qua quá trình khảo sát Bờm có lên thang điểm về độ đẹp cho mỗi thành phố. Độ đẹp của thành phố thứ \(i\) được đánh giá là \(a_i\).

Việc đi lại giữa các thành phố được thực hiện bằng xe buýt. Cách vận hành xe buýt ở đây cũng rất đặc biệt:

Giả sử xe buýt đang ở thành phố \(u\), nó sẽ xác định tuyến đi tiếp theo bằng cách chọn một thành phố \(v\) (\(v \neq u\) và có thể \((u,v)\) không có cạnh nối) sao cho giá trị \(a_v - d(u, v)\) là lớn nhất. Trong đó \(d(u, v)\) được định nghĩa là khoảng cách đi từ \(u\) đến \(v\). Nếu có nhiều thành phố thỏa mãn thì xe buýt sẽ di chuyển đến thành phố có chỉ số nhỏ nhất. Khi đã chọn được điểm đến là thành phố \(v\), xe buýt sẽ đi thẳng từ \(u\) đến \(v\) mà không dừng ở các thành phố trung gian.

Yêu cầu: Cho \(Q\) truy vấn, mỗi truy vấn có hai tham số \(s, k\) ứng với việc Bờm xuất phát từ thành phố \(s\) và di chuyển qua \(k\) tuyến đường bằng xe buýt theo cách mô tả ở trên. Hãy cho biết, với mỗi truy vấn thì Bờm sẽ kết thúc chuyến đi ở thành phố nào?

Input

• Dòng đầu chứa hai số nguyên dương \(n, Q\) (\(n, Q \leq 2 \times 10^5\)) là số thành phố và số truy vấn.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) là độ đẹp của các thành phố (\(|a_i| \leq 10^9\)).
• \(n - 1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(x, y, w\) mô tả một con đường hai chiều (\(1 \leq x, y \leq n,~ 0 < w \leq 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(s, k\) mô tả một truy vấn: thành phố xuất phát \(s\) và số tuyến đường \(k\) (\(1 \le s \le n\), \(k \le 10^6\)).

Output

Gồm \(Q\) dòng, mỗi dòng in ra chỉ số thành phố mà Bờm sẽ kết thúc chuyến đi ở mỗi truy vấn.

Example

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

5
3
3
1

Scoring

• Có 20% số test với \(n, Q \leq 200,~ k \leq 200\).
• Có 25% số test khác với \(n, Q \leq 2000\).
• Có 25% số test khác với \(k = 1\).
• Số test còn lại không có ràng buộc gì thêm.

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

Bạn cần thực hiện \(q\) truy vấn thuộc một trong hai loại sau:

• Thay đổi giá trị: Gán giá trị của đỉnh \(s\) thành \(x\).
• Tính tổng đường đi: Tính tổng giá trị của tất cả các đỉnh trên đường đi từ gốc (đỉnh \(1\)) đến đỉnh \(s\) (bao gồm cả hai đầu).

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 đỉnh của cây 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)\) --- giá trị ban đầu của các đỉnh.

\(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\) \((1 \le a, b \le n)\) --- mô tả một cạnh nối giữa hai đỉnh \(a\) và \(b\). Đảm bảo các cạnh này tạo thành một cây.

\(q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn:

• Dạng 1 s x \((1 \le s \le n, 1 \le x \le 10^9)\): thay đổi giá trị của đỉnh \(s\) thành \(x\).
• Dạng 2 s \((1 \le s \le n)\): tính tổng giá trị các đỉnh trên đường đi từ đỉnh \(1\) đến đỉnh \(s\).

Output

Với mỗi truy vấn loại 2, in ra một dòng chứa tổng giá trị cần tìm.

Example

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

11
8

Kể từ khi IOI, thành phố Pattaya sẽ tổ chức cuộc đua Olympic quốc tế về đua tốc độ (IOR) 2011. Ban tổ chức phải tìm ra vòng đua tốt nhất cho cuộc thi này.

Ở vùng Pattaya - Chonburi, có \(N\) thành phố được nối với nhau bởi mạng gồm \(N-1\) đường cao tốc. Mỗi đường cao tốc đều cho phép đi theo cả hai chiều, nối hai thành phố phân biệt và có độ dài đo bằng kilomet là số nguyên. Ngoài ra, có đúng một đường đi giữa cặp hai thành phố bất kỳ, nghĩa là đây là một cấu trúc cây.

Cuộc thi IOR có quy tắc đặc biệt: một vòng đua phải có độ dài đúng \(K\) kilomet, bắt đầu và kết thúc ở hai thành phố phân biệt. Để tối ưu hóa việc tổ chức, vòng đua phải sử dụng ít đường cao tốc nhất có thể.

Yêu cầu: Bạn hãy cho biết số lượng đường cao tốc nhỏ nhất trên vòng đua hợp quy tắc có độ dài đúng \(K\). Nếu không tìm được vòng đua nào như vậy, kết quả sẽ là \(-1\).

Input

Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu chứa hai số nguyên \(N\) và \(K\) (\(1 \le N \le 2 \cdot 10^5\), \(1 \le K \le 10^9\)).
• \(N-1\) dòng tiếp theo, mỗi dòng ghi 3 số \(u, v, l\) (\(1 \le u, v \le N\)), với \(u\) và \(v\) là hai thành phố nối với nhau bằng một đường cao tốc có độ dài \(l\) (\(1 \le l \le 10^9\)).

Output

In ra một số nguyên duy nhất là kết quả của bài toán.

Example

4 3
0 1 1
1 2 2
1 3 4

2

3 3
0 1 1
1 2 1

-1

11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7

2

Scoring

• Subtask 1 (9 điểm): \(1 \le N \le 100, 1 \le K \le 100\). Đỉnh \(i\) sẽ nối đến đỉnh \(i + 1\).
• Subtask 2 (12 điểm): \(1 \le N \le 1000, 1 \le K \le 1000000\).
• Subtask 3 (22 điểm): \(1 \le N \le 200\,000, 1 \le K \le 100\).
• Subtask 4 (57 điểm): Không có giới hạn gì thêm.

Cho hai cây \(A\) và \(B\) đều gồm \(n\) đỉnh, mỗi đỉnh được đánh số từ \(1\) đến \(n\). Với mỗi cây, bạn được biết thông tin về cha của từng đỉnh:

• Trên cây \(A\), \(a_i\) là cha của đỉnh \(i\). Nếu \(u\) là gốc cây \(A\) thì \(a_u = -1\).
• Trên cây \(B\), \(b_i\) là cha của đỉnh \(i\). Nếu \(v\) là gốc cây \(B\) thì \(b_v = -1\).

Một đỉnh \(x\) được gọi là tổ tiên của đỉnh \(y\) trên một cây nếu tồn tại một dãy các đỉnh \(z_1, z_2, \dots, z_k\) sao cho \(z_1 = x\), \(z_k = y\) và với mỗi \(j\), \(z_j\) là cha của \(z_{j+1}\).

Một cặp đỉnh \((u, v)\) được gọi là thỏa mãn nếu \(u\) là tổ tiên của \(v\) trên cả cây \(A\) và cây \(B\).

Nhiệm vụ: Hãy đếm xem có bao nhiêu cặp \((u, v)\) thỏa mãn như vậy.

\InputFile

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \le n \le 10^6)\).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(a_i\) và \(b_i\) --- cha của đỉnh \(i\) trên cây \(A\) và cây \(B\) \((1 \le a_i, b_i \le n\) hoặc \(-1\) nếu là gốc).

\OutputFile

• In ra một số nguyên duy nhất --- số cặp \((u, v)\) sao cho \(u\) là tổ tiên của \(v\) trên cả hai cây.

\Scoring

• Subtask 1 (25%): \(n \le 100\)
• Subtask 2 (25%): \(n \le 2000\)
• Subtask 3 (25%): \(n \le 10^5\)
• Subtask 4 (25%): Không có giới hạn thêm

Example

3
-1 -1
1 3
1 1

2