Contest Câu Cá Vạn Cân (Div.01) - Pre THT B, C1, C2 - 2026

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
A Caucavancan Div.01 - Problem A - A Fish Catching Trip 100 (p) 1.0s 256M
B Caucavancan Div.01 - Problem B - Bí Cảnh Fishing Team 100 (p) 1.0s 256M
C Caucavancan Div.01 - Problem C - Check Perfect Sub-array 100 (p) 1.0s 256M
D Caucavancan Div.01 - Problem D - Dieu Hoi's Relationship Queries 100 (p) 1.0s 256M
E Caucavancan Div.01 - Problem E - Encroachment of Zero-Point Corruption 100 (p) 1.0s 256M
F Caucavancan Div.01 - Problem F - Find "Centroid" of relationship tree 100 (p) 2.0s 256M

A. Caucavancan Div.01 - Problem A - A Fish Catching Trip

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: prba.inp Output: prba.out

Sau trận chiến tại Hắc Hải, trongphithien và p2o2HuaGiaBao không còn đánh nhau bằng oán khí nữa mà chuyển sang đấu trí bằng "Ván cờ linh ngư". Họ bày ra một hàng \(n\) con cá được sắp xếp theo độ linh lực khác nhau trên một dải đá.
trongphithien nắm giữ quyền điều khiển một dải đá từ trái, còn p2o2HuaGiaBao điều khiển từ phải. Họ cần chọn ra một mảng con của dải đá sao cho tổng linh lực của đoạn đó đúng bằng một giá trị mục tiêu \(K\) để kích hoạt cấm thuật. Nếu vượt quá \(K\), trận pháp sẽ bị phản phệ. trongphithien và p2o2HuaGiaBao đang tranh giành xem ai sẽ là người tìm ra độ dài dài nhất của đoạn con đó để kết thúc ván cờ.
Yêu cầu: Cho dãy số nguyên dương \(A\) có \(n\) phần tử (\(A_i > 0\)). Hãy tìm độ dài lớn nhất của một mảng con có tổng bằng \(K\). Nếu không có đoạn nào thỏa mãn, in ra -1.

Input

  • Dòng đầu tiên gồm \(2\) số nguyên dương \(n\) và \(K\) (\(1 \le n \le 10^6, 1 \le K \le 10^9\)).
  • Dòng hai gồm \(n\) số nguyên dương \(A_1, A_2, \dots, A_n\) (\(1\le A_i \le 10^9\)).

Output

  • Gồm \(1\) dòng duy nhất là độ dài lớn nhất của đoạn con có tổng bằng \(K\), hoặc -1 nếu không tồn tại.

Example

Test 1

Input 
5 7
2 3 1 2 4
Output 
3
Note
  • Đoạn \([\)\(3; 1; 2\)\(]\) tổng bằng \(6\ne 7\)
  • Đoạn \([\)\(3; 4\)\(]\) tổng bằng \(7=7\), độ dài là \(2\)
  • Đoạn \([\)\(2; 1; 4\)\(]\) tổng là \(7=7\), độ dài là \(3\).
    \(\rightarrow\) Vậy, độ dài dài nhất của đoạn thỏa mãn đề bài là \(3\).

Test 2

Input 
10 500000
2753 3593 1592 2920 4931 48011 20000 5000 30000 10000
Output 
-1

B. Caucavancan Div.01 - Problem B - Bí Cảnh Fishing Team

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: prbb.inp Output: prbb.out

Cuộc chiến giữa Hiệp Hội Câu Cá và Chi Điếu Hội đã bước vào giai đoạn sống còn. Bên phía Hiệp Hội Câu Cá, hai cao thủ trongphithien và p2o2HuaGiaBao đang dốc toàn lực bảo vệ Bí Cảnh Câu Cá. Tuy nhiên, Tam Hoàng của Chi Điếu Hội đã tung ra "Hắc Ngư Trận", một ma trận oán khí bao phủ toàn bộ vùng biển, khiến các cần câu của Hiệp Hội không thể định vị được cá. Để phá giải, trongphithien đã tính toán ra rằng ma trận oán khí này thực chất là một lưới tọa độ chứa các chỉ số phong ấn. trongphithien đã hi sinh một phần linh lực để giải mã ma trận, còn p2o2HuaGiaBao đang chờ đợi kết quả từ bạn để kích hoạt đòn phản công cuối cùng. Bạn chính là hy vọng duy nhất của Hiệp Hội để tìm ra vùng có oán khí cao nhất, nơi Tam Hoàng đang ẩn nấp để điều khiển trận pháp.

Input

  • Dòng đầu tiên chứa 4 số nguyên dương \(M, N, a, b\) (\(1 \le a \le M \le 3000, 1 \le b \le N \le 3000\)).
  • \(M\) dòng tiếp theo với mỗi dòng chứa \(N\) số nguyên, đại diện cho mức độ oán khí \(A_{i_j}\) tại tọa độ \((i, j)\) của Hắc Ngư Trận (giá trị mỗi phần tử nằm trong khoảng \([-10^4, 10^4]\)).

Output

  • In ra một số nguyên duy nhất là tổng mức oán khí lớn nhất có thể đạt được bằng cách đặt trận pháp phong ấn hình chữ nhật kích thước \(a \times b\).

Example

Test 1

Input 
3 3 2 2
-10 20 30
40 50 -60
70 80 -90
Output 
240
Note

Có tổng cộng 4 vùng có thể đặt trận pháp \(2 \times 2\):

  • Góc trên trái: \((-10) + 20 + 40 + 50 = 100\)
  • Góc trên phải: \(20 + 30 + 50 + (-60) = 40\)
  • Góc dưới trái: \(40 + 50 + 70 + 80 = 240\)
  • Góc dưới phải: \(50 + (-60) + 80 + (-90) = -20\)

\(\rightarrow\) Trong \(4\) vùng này, giá trị \(240\) là lớn nhất. Do đó, chương trình cần xuất ra kết quả là 240.

Test 2

Input 
3 3 2 2
9340 3057 9248
-8142 -4849 -1256
-7986 -5737 -2908
Output 
6200

C. Caucavancan Div.01 - Problem C - Check Perfect Sub-array

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: prbc.inp Output: prbc.out

Mình hợp nhau đến như vậy thế nhưng không phải là yêu
Và em muốn hỏi anh rằng, chúng ta là thế nào?
Rồi lặng người đến vô tận, trách sao được sự tàn nhẫn
Anh trót vô tình, thương em như là em gái

Đừng lo lắng về em khi mà em vẫn còn yêu anh
Càng xa lánh, càng trống vắng, tim cứ đau và nhớ lắm
Đành phải buông hết tất cả thôi
Nụ cười mỉm sau bờ môi
Ấm áp dịu dàng vai anh
Em đã bao lần yên giấc

Nhìn trên cao khoảng trời yêu mà em lỡ dành cho anh
Giờ mây đen quyện thành bão, giông tố đang dần kéo đến
Chồi non háo hức đang đợi mưa
Rất giống em ngày xưa
Mưa trôi để lại ngây thơ trong giấc mơ buốt lạnh
Trích Em Gái Mưa (Hương Tràm)

Khúc ca vẫn còn vang lên và vẫn còn mãi trong lòng những giới trẻ thời 9x thậm chí là đến bây giờ. p2o2HuaGiaBao là một người trẻ sống hòa đồng. Nhưng có những lúc anh ấy gặp khó khắn. Ban đầu, lúc cậu ấy còn là một học sinh cấp \(1\). Anh ta đã có thân thiết với một người bạn khác. Lúc ấy, hai người bạn đó đã không ngừng giúp đỡ nhau từ việc bình thường và nhỏ nhặt nhất cho đến những chuyện học tập, giải trí, ... Ngoài ra, hai người bạn còn thường xuyên trò chuyện, tâm sự, cũng như tặng những món quà tràn đầy ý nghĩa. Mọi chuyện tốt đẹp cho đến khi trongphithien xen vào.
Vì trongphithien đều bị các bạn khác cô lập nên luôn bị FA. Chính vì vậy, anh ấy lên một kế hoạch hoàn hảo là sẽ nói dối với cô bạn thân thiết nhất của cậu ta rằng p2o2HuaGiaBao bắt cá hai tay để có thể dễ dàng làm quen với cô gái này. Ngay khi chuẩn bị thủ đoạn không đẹp của trongphithien thì vô tình bị cô bạn ấy phát hiện và nói với p2o2HuaGiaBao.
Khoảng một tuần sau đó, tin này đã lan ra khắp trường. Lần này không chỉ bạn bè trong lớp hay trường xa lánh mà còn bị sự phê phán của gia đình và thầy cô.
Thi join contest của HGBCpp_ cậu ta bị bí câu này nhưng vì ai ai cũng ghét anh ta hết nên không biết phải nhờ sự trợ giúp ở đâu. Các bạn hãy giúp cậu ấy bài toán dưới đây nhé! Bài toán như sau.
Cho một dãy gồm \(N\) phần tử, phần tử thứ \(i\) có giá trị nguyên \(a_i\). Ta gọi một đoạn con liên tiếp là ổn định nếu tổng các phần tử trên đoạn đó chia hết cho \(3\), đồng thời trong đoạn đó không tồn tại hai phần tử kề nhau cùng mang cùng một giá trị chẵn/lẻ theo thứ tự hiện tại của dãy. Ban đầu dãy được cho trước, sau đó có \(Q\) thao tác online gồm hai loại:

  1. Truy vấn cập nhật: 1 x y nghĩa là gán \(a_x=y\)
  2. Truy vấn câu hỏi: 2 l r nghĩa là xét đoạn \([l,r]\).
    Với mỗi truy vấn loại 2, hãy tìm giá trị lớn nhất của một đoạn con ổn định nằm hoàn toàn trong \([l,r]\). Nếu không tồn tại đoạn con ổn định nào thì in ra 0.

Input

  • Dòng đầu tiên chứa hai số nguyên \(N,Q\). \((1\le N,Q\le 2\cdot10^5)\)
  • Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,\dots,a_N\). \((-10^9\le a_i\le 10^9)\)
  • \(Q\) dòng tiếp theo, mỗi dòng là một thao tác thuộc một trong hai dạng sau: 1 x y, 2 l r.

Output

  • Với mỗi truy vấn loại 2, in ra một số nguyên duy nhất là giá trị lớn nhất tìm được, hoặc 0 nếu không tồn tại đoạn con ổn định.

Example

Test 1

Input 
6 6
2 1 4 3 5 6
2 1 6
1 3 1
2 1 4
1 2 8
2 2 5
2 3 6
Output 
6
3
9
6
Note

Truy vấn 1

  • Cho trước dãy:
    2 1 4 3 5 6
  • Cho trước truy vấn:
    2 1 6

    \(\rightarrow\) Ta xét các đoạn con có tổng chia hết cho \(3\) và các phần tử luân phiên chẵn lẻ.
  • Các đoạn thỏa mãn gồm:
    [1,2] = 2 + 1 = 3
[1,5] = 2 + 1 + 4 + 3 + 5 = 15
[6,6] = 6
  • Trong số đó, giá trị lớn nhất là:
    6
  • Do đó kết quả truy vấn là:
    6

Truy vấn 2

  • Cho trước thao tác cập nhật:
    1 3 1
  • Dãy trở thành:
    2 1 1 3 5 6
  • Cho trước truy vấn:
    2 1 4
  • Ta xét đoạn:
    2 1 1 3
  • Các đoạn thỏa mãn gồm:
    [1,2] = 3
[4,4] = 3
  • Giá trị lớn nhất là:
    3
  • Do đó kết quả truy vấn là:
    3

Truy vấn 3

  • Cho trước thao tác cập nhật:
    1 2 8
  • Dãy trở thành:
    2 8 1 3 5 6
  • Cho trước truy vấn:
    2 2 5
  • Ta xét đoạn:
    8 1 3 5
  • Các đoạn thỏa mãn gồm:
    [2,3] = 8 + 1 = 9
[4,4] = 3
  • Giá trị lớn nhất là:
    9
  • Do đó kết quả truy vấn là:
    9

Truy vấn 4

  • Cho trước truy vấn:
    2 3 6
  • Ta xét đoạn:
    1 3 5 6
  • Các đoạn thỏa mãn gồm:
    [4,4] = 3
[6,6] = 6
  • Giá trị lớn nhất là:
    6
  • Do đó kết quả truy vấn là:
    6

Test 2

Input 
5 4
8392 3910 392 4203 1039
1 3 547
1 4 893
2 1 5
2 4 5
Output 
0
0

D. Caucavancan Div.01 - Problem D - Dieu Hoi's Relationship Queries

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: prbd.inp Output: prbd.out

Ohh...
Anh như trẻ lạc còn tâm tối giữa rừng thông
Nơi cánh chim nhỏ lạc đàn tìm bến đỗ để ngừng trông
Anh là một con đom đóm mắt anh sáng đến xoay vòng
Gieo cho anh cả một mầm sống nhưng chẳng chịu công vun trồng
Vì lúc ấy ta còn trẻ nên đời bạc và mưu sinh
Anh chưa học hết lớp 10 người ta gọi là lưu linh
Anh gắn bó với sông nước và cảnh vật này hữu tình
Còn người ta cho em áo lụa hỏi tại sao chẳng phụ mình

Tình yêu ơi bình yên ơi về đây đi để anh ôm
Để gió cuốn đêm nay ai đưa về nhà để gió vang lên câu tình ca
Để lệ hoen mi khi mùa xuân đang thầm thì nhìn người mà ra đi anh chẳng níu kéo điều gì
Mà nghe sao đáng thương nhìn nhau như cố hương
Tìm em ở bốn phương vì say nên vấn vương ...
Trích Hồng Nhan Bạc Phận (J97)

Tại Bến Tre, nơi sinh ra và lớn lên của Jack97. Có một cái cây thần bí tên \(\texttt{Cây Linh Ngư}\). Đây chính là cái cây truyền thống và người dân thường dùng để biểu diễn gia phả giữa các mối quan hệ trong gia đình, dòng họ. trongphithien và p2o2HuaGiaBao đã thâm nhập được vào thánh địa của \(\texttt{Chi Điếu Hội}\) \(\text{---}\) nơi tồn tại cái cây thần bí đó. Tại đây, họ phát hiện ra một cây gia phả cổ xưa gọi là \(\texttt{Cây Linh Ngư}\), gồm \(n\) nút đại diện cho các thủ lĩnh linh hồn, kết nối với nhau bởi các nhánh kênh. Mỗi nút trên cây có một giá trị linh lực \(v_i\). Để phong ấn toàn bộ Chi Điếu Hội, họ cần chọn ra một tập hợp các nút sao cho không có hai nút nào được chọn mà lại có mối quan hệ cha-con trực tiếp (tập độc lập), đồng thời tổng linh lực của các nút được chọn phải là lớn nhất.
Yêu cầu: Cho một cây có \(n\) nút, mỗi nút có giá trị \(v_i\). Hãy tìm tập độc lập có tổng giá trị các nút lớn nhất.

Input

  • Dòng đầu: số nguyên \(n\) (\(2 \le n \le 2 \cdot 10^5\)).
  • Dòng hai: \(n\) số nguyên \(v_i\) (\(|v_i| \le 10^9\)).
  • \(n-1\) dòng tiếp theo: Mỗi dòng gồm \(u, v\) thể hiện một cạnh nối giữa hai nút.

Output

  • In ra giá trị tổng linh lực lớn nhất tìm được.

Example

Test 1

Input 
5
10 20 30 40 50
1 2
1 3
2 4
2 5
Output 
120
Note

Đây là cách chọn nút để có tổng 120:
Cây: 1(10) là gốc. 2(20) & 3(30) là con của 1. 4(40) & 5(50) là con của 2.
Quy tắc: Không chọn cặp cha-con trực tiếp (1-2, 1-3, 2-4, 2-5).
Cách chọn:

  • Chọn nút 3 (giá trị 30).
  • Chọn nút 4 (giá trị 40).
  • Chọn nút 5 (giá trị 50).

\(\rightarrow\) Tổng: \(30 + 40 + 50 = 120\).

Tập hợp \([\)\(3, 4, 5\)\(]\) không có nút nào là cha-con trực tiếp của nhau, nên thỏa mãn điều kiện.

Test 2

Input 
3
657168938 -230210953 -95301331
2 1
3 2
Output 
657168938

E. Caucavancan Div.01 - Problem E - Encroachment of Zero-Point Corruption

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: prbe.inp Output: prbe.out

Tại Thư viện Cổ đại, trongphithien và p2o2HuaGiaBao phát hiện ra rằng mỗi ký tự trong "Xâu Khởi Nguyên" sở hữu một trọng số năng lượng ẩn sau mỗi lần xuất hiện. Khi "Zero-Point Corruption" xâm chiếm, các ký tự thay đổi vị trí kéo theo sự hỗn loạn năng lượng.
Cho xâu \(S\) độ dài \(n\) gồm các chữ cái thường và một hằng số khoảng cách \(K\). Mỗi vị trí \(i\) trên xâu có một mức năng lượng cố định ban đầu là \(V_i\). Thực hiện \(Q\) truy vấn thuộc hai loại:

  • Loại \(1\) (1 i c): Thay đổi ký tự tại vị trí \(i\) thành ký tự \(c\). Mức năng lượng \(V_i\) tại vị trí đó được giữ nguyên không đổi.
  • Loại \(2\) (2 L R c): Chọn một tập hợp các vị trí \(i_1, i_2, \dots, i_m\) nằm trong đoạn \([L, R]\) sao cho:
  • Tất cả các vị trí được chọn đều đang chứa ký tự \(c\) (\(S_{i_j} = c\)).
  • Khoảng cách giữa hai vị trí liên tiếp được chọn phải cách nhau ít nhất một khoảng cách \(K\) (tức là \(i_j - i_{j-1} \ge K\) với mọi \(j \ge 2\)).
  • Tổng giá trị năng lượng \(V_{i_1} + V_{i_2} + \dots + V_{i_m}\) đạt giá trị lớn nhất.

Input

  • Dòng đầu tiên gồm ba số nguyên \(n, Q, K\) (\(1 \le n, Q \le 5\times 10^4; 1 \le K \le n\)).
  • Dòng thứ hai gồm một xâu \(S\) độ dài \(n\) gồm các ký tự chữ cái latin thường từ a đến z.
  • Dòng thứ ba gồm \(n\) số nguyên \(V_1, V_2, \dots, V_n\) (\(1 \le V_i \le 10^9\)) — mảng năng lượng cố định tại mỗi vị trí.
  • \(Q\) dòng tiếp theo: Mỗi dòng mô tả một truy vấn:
    • Truy vấn loại \(1\): 1 i c (với \(1 \le i \le n\) và \(c\) là ký tự thường).
    • Truy vấn loại \(2\): 2 L R c (với \(1 \le L \le R \le n\) và \(c\) là ký tự thường).

Output

  • Với mỗi truy vấn loại \(2\), in ra một số nguyên duy nhất trên một dòng là tổng giá trị năng lượng tối ưu lớn nhất tìm được. Nếu không có ký tự \(c\) nào trong đoạn, in ra 0.

Example

Test 1

Input 
7 3 3
abcabca
1 10 5 2 8 3 6
2 1 7 a
1 4 b
2 1 7 a
Output 
9
7
Note

  • Truy vấn \(1\) (2 1 7 a): Tìm chuỗi ký tự a tối ưu trong đoạn \([1, 7]\).

    • Các vị trí có ký tự a là: \(1, 4, 7\).
    • Khoảng cách giữa các vị trí: \(\vert{}4 - 1\vert{} = 3 \ge K\); \(\vert{}7 - 4\vert{} = 3 \ge K\).
    • Ta có thể chọn cả 3 vị trí này. Tổng năng lượng tối đa: \(V_1 + V_4 + V_7 = 1 + 2 + 6 = \mathbf{9}\).

  • Truy vấn 2 (1 4 b): Thay đổi ký tự tại vị trí \(4\) từ a thành b. Xâu mới trở thành abcbcba. Mảng năng lượng \(V\) giữ nguyên.

  • Truy vấn 3 (2 1 7 a): Tiếp tục tìm chuỗi ký tự a tối ưu trong đoạn \([1, 7]\).

    • Do vị trí \(4\) đã đổi thành b, các vị trí có ký tự a lúc này chỉ còn: \(1, 7\).
    • Khoảng cách giữa chúng: \(\vert{}7 - 1\vert{} = 6 \ge K\).
    • Tổng năng lượng tối đa: \(V_1 + V_7 = 1 + 6 = \mathbf{7}\).

Test 2

Input 
6 2 2
aaaaaa
10 20 5 30 2 15
2 1 6 a
1 4 c
Output 
65

F. Caucavancan Div.01 - Problem F - Find "Centroid" of relationship tree

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: prbf.inp Output: prbf.out

Tại thời nhà \(\texttt{Minh(明)}\), nhà vua p2o2HuaGiaBao nhận thấy mỗi người dân có rất nhiều mối quan hệ. Có những người có \(3\) đời dòng họ thậm chí tận \(9\) đến \(10\) dòng họ.

Để tiện quản lý, nhà vua yêu cầu sau khi sinh xong một đứa con cần đến cơ quan để đăng kí vào Cây Gia Phả để có thể thực hiện \(\text{Tru di tam/cửu tộc (灭族三代或九代)}\) khi vi phạm pháp luật một cách triệt để. Nhà vua p2o2HuaGiaBao muốn thực hiện một số thao tác trên các Cây Gia Phả để rèn luyện tư duy cho các thái giám (PhuocThien, uou). Hoàng tử trongphithien nói rằng:

Nếu ai không giải được bài toán của đức vua sẽ bị đuổi vĩnh viễn khỏi danh sách thái giám trong hoàng cung.

Thật vậy, không ai giải được bài toán này nên vì lượng test case lớn và bài toán quá khó với họ nên nhờ các coder tài năng tương lai đến giúp họ. Bài toán khó nhằn ấy như sau:

Xét một một mạng lưới mối quan hệ dạng cây (Relationship Tree) gồm \(n\) thành viên được đánh số từ \(1\) đến \(n\). Mỗi thành viên \(i\) ban đầu sở hữu một chỉ số ảnh hưởng là \(val_i\). Có \(q\) truy vấn thuộc \(3\) loại sau:

  • Loại \(1\) (1 u c x mod): Thực hiện một chiến dịch truyền thông từ người đứng đầu nhóm \(u\). Tất cả các thành viên thuộc cây con gốc \(u\) (nhóm do \(u\) quản lý) được tăng chỉ số ảnh hưởng thêm một lượng bằng: \(\lfloor (c \times x) / mod \rfloor\).
  • Loại \(2\) (2 u v c): Cần thiết lập một cầu nối liên lạc ngắn nhất từ thành viên \(u\) đến thành viên \(v\). Hãy tính tổng chỉ số ảnh hưởng của tất cả các thành viên nằm trên lộ trình kết nối này, sau đó cộng thêm một chi phí phát sinh là \(c\).
  • Loại \(3\) (3 u p1 p2 p3): Tìm trọng tâm (Centroid) của cây con gốc \(u\) (nhóm do \(u\) quản lý). Trọng tâm là thành viên mà nếu ta chọn người đó làm đại diện điều hành nhóm, thì không có một nhánh cấp dưới trực thuộc nào (xét riêng trong phạm vi cây con gốc \(u\)) chiếm quá một nửa tổng số thành viên của cả nhóm. Ba tham số \(p_1, p_2, p_3\) là các mã bảo mật hệ thống (nhiễu dữ liệu) cần được đọc vào nhưng không ảnh hưởng đến vị trí trọng tâm.

Input

  • Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 250000\)) — tương ứng là số lượng đỉnh của cây và số lượng câu hỏi truy vấn.
  • Dòng thứ hai chứa \(n\) số nguyên cách nhau bởi khoảng trắng \(val_1, val_2, \dots, val_n\) (\(1 \le val_i \le 10^9\)) — biểu diễn mức năng lượng ảnh hưởng ban đầu của từng đỉnh từ \(1\) đến \(n\).
  • \(n - 1\) dòng tiếp theo: Mỗi dòng chứa hai số nguyên \(u\) và \(v\) (\(1 \le u, v \le n, u \ne v\)) — mô tả một cạnh nối không hướng giữa đỉnh \(u\) và đỉnh \(v\) trên cây. Dữ liệu bảo đảm các cạnh tạo thành một cấu trúc cây liên thông hợp lệ.
  • \(q\) dòng cuối cùng: Mỗi dòng mô tả một truy vấn thuộc một trong ba dạng sau:
    • Truy vấn loại \(1\): 1 u c x mod với \(1 \le u \le n\) và \(1 \le c, x, mod \le 1000\).
    • Truy vấn loại \(2\): 2 u v c với \(1 \le u, v \le n\) và \(0 \le c \le 10^6\).
    • Truy vấn loại \(3\): 3 u p1 p2 p3 với \(1 \le u \le n\) và \(1 \le p_1, p_2, p_3 \le 1000\) (các tham số nhiễu).

Output

  • Với mỗi truy vấn loại \(2\) hoặc loại \(3\), in ra kết quả tính toán được trên một dòng riêng biệt theo đúng thứ tự xuất hiện của chúng trong file dữ liệu đầu vào.
  • Kết quả của truy vấn loại \(2\) là một số nguyên duy nhất.
  • Kết quả của truy vấn loại \(3\) là một số nguyên duy nhất chỉ số của đỉnh đóng vai trò là trọng tâm của cây con đó. Nếu có nhiều trọng tâm hợp lệ, thí sinh có thể in ra bất kỳ đỉnh nào thỏa mãn tính chất. Đề bài đảm bải truy vấn có lời giải.

Example

Test 1

Input 
5 4
10 20 30 40 50
1 2
1 3
2 4
2 5
1 2 5 10 2
2 4 5 15
3 2 100 200 300
2 1 3 0
Output 
200
2
40
Note
  • Cấu trúc cây ban đầu: Gốc tại thành viên \(1\). Thành viên \(1\) nối với thành viên \(2\) và \(3\). Thành viên \(2\) nối với \(4\) và \(5\).
  • Mức độ ảnh hưởng ban đầu: \(val = [10, 20, 30, 40, 50]\)
  • Truy vấn \(1\) (1 2 5 10 2): Cập nhật nhóm thành viên thuộc cây con gốc \(2\) (gồm các thành viên: \(2, 4, 5\)).
    • Lượng ảnh hưởng tăng thêm: \(\lfloor (5 \times 10) / 2 \rfloor = 25\).
    • Mức ảnh hưởng mới của cây: \(val = [10, 45, 30, 65, 75]\).
  • Truy vấn \(2\) (2 4 5 15): Tính tổng năng lượng trên đường đi từ \(4\) đến \(5\) rồi cộng thêm hằng số \(15\).
    • Cách liên lạc từ \(4\) đến \(5\) là: \(4 \rightarrow 2 \rightarrow 5\).
    • Tổng trọng số ảnh hưởng trên đường đi: \(val_4 + val_2 + val_5 = 65 + 45 + 75 = 185\).
    • Kết quả xuất ra: \(185 + 15 = 200\).
  • Truy vấn \(3\) (3 2 100 200 300): Tìm trọng tâm của các thành viên do \(2\) quản lý (nhánh con chứa các thành viên \(2, 4, 5\)).
    • Kích thước cây con này là \(3\) thành viên. Nếu chọn đỉnh \(2\) làm trọng tâm, các nhánh con tách ra từ nó (\(4\) và \(5\)) đều có kích thước là \(1\) (không vượt quá một nửa kích thước cây con là \(\lfloor 3 / 2 \rfloor = 1\)).
    • Do đó, đỉnh \(2\) chính là trọng tâm hợp lệ. Ba tham số 100 200 300 là tham số nhiễu, được đọc vào và bỏ qua.
  • Truy vấn \(4\) (2 1 3 0): Tính tổng trọng số ảnh hưởng trên đường đi từ \(1\) đến \(3\) rồi cộng thêm \(0\).
    • Đường đi: \(1 \rightarrow 3\). Tổng năng lượng: \(val_1 + val_3 = 10 + 30 = 40\).
    • Kết quả xuất ra: \(40 + 0 = 40\).

Test 2

Input 
4 3
5 5 5 5
1 2
2 3
3 4
1 2 10 10 3
3 1 9 9 9
2 1 4 100
Output 
2
219