Vương quốc JOI có \(N\) thành phố đánh số từ \(1\) đến \(N\) và \(N-1\) quốc lộ đánh số từ \(1\) đến \(N-1\). Có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác qua các quốc lộ. Thành phố \(i\) có độ nổi tiếng là một số nguyên không âm, ban đầu bằng \(C_i\); quốc lộ \(j\) nối hai thành phố \(A_j,B_j\) theo cả hai chiều và có thời gian đi lại là một số nguyên dương, ban đầu bằng \(D_j\).

Mỗi thành phố có một vạc lửa. Theo truyền thống lễ hội, việc thắp vạc là tín hiệu để các đoàn diễu hành xuất phát từ thành phố đó. Hai thành phố được gọi là kề nhau nếu có một quốc lộ nối trực tiếp chúng. Ngay khi vạc của một thành phố được thắp tại thời điểm \(t\), với mỗi thành phố kề, một đoàn diễu hành riêng xuất phát đến đó và đến nơi tại thời điểm \(t+d\), trong đó \(d\) là thời gian đi lại của quốc lộ nối hai thành phố.

Một số thành phố thắp lửa ngay khi lễ hội bắt đầu, còn các thành phố khác chờ lễ hội đủ sôi động. Gọi thời điểm bắt đầu lễ hội là \(0\). Thành phố có độ nổi tiếng \(0\) thắp lửa ở thời điểm \(0\). Nếu độ nổi tiếng là \(c\ge1\), nó thắp lửa tại thời điểm đầu tiên mà số đoàn diễu hành đã đến từ các thành phố kề đạt ít nhất \(c\); nếu điều này không xảy ra thì vạc không bao giờ được thắp.

Ông K sẽ ở lại vương quốc JOI. Trong thời gian đó có \(Q\) sự kiện, đánh số từ \(1\) đến \(Q\) theo thứ tự từ sớm đến muộn. Sự kiện thứ \(k\) thuộc một trong ba loại:

• Loại \(1\): độ nổi tiếng của thành phố \(V_k\) đổi thành \(X_k\).
• Loại \(2\): thời gian đi lại của quốc lộ \(E_k\) đổi thành \(X_k\).
• Loại \(3\): ông K đến thành phố \(V_k\). Giả sử lễ hội bắt đầu ngay lúc này, hãy xác định vạc của thành phố đó có được thắp hay không và nếu có thì được thắp tại thời điểm nào.

Mỗi truy vấn loại 3 mô phỏng một lễ hội mới bắt đầu tại thời điểm \(0\) bằng các giá trị hiện hành; truy vấn không làm thay đổi độ nổi tiếng, thời gian đi lại hay trạng thái dùng cho sự kiện sau.

Dữ liệu vào

Dòng đầu là \(N\). \(N-1\) dòng tiếp theo gồm \(A_j,B_j,D_j\). \(N\) dòng sau đó là \(C_1,\ldots,C_N\). Dòng tiếp theo là \(Q\).

Tiếp theo là \(Q\) dòng, mỗi dòng mô tả một sự kiện. Số nguyên đầu tiên \(P_k\) là loại sự kiện, thuộc \(\{1,2,3\}\). Mỗi sự kiện có dạng 1 V X (đổi \(C_V\) thành \(X\)), 2 E X (đổi \(D_E\) thành \(X\)), hoặc 3 V (truy vấn thành phố \(V\)).

Dữ liệu ra

Với mỗi sự kiện loại 3, theo thứ tự thời gian của các sự kiện, in thời điểm vạc được thắp; in -1 nếu không bao giờ được thắp.

Ràng buộc

• \(2\le N\le150\,000\).
• \(1\le Q\le150\,000\).
• \(0\le C_i\le N\), \(1\le A_j<B_j\le N\), \(1\le D_j\le10^6\).
• Cây liên thông; mọi giá trị đầu vào là số nguyên.
• Với sự kiện loại 1: \(1\le V\le N\) và \(0\le X\le N\).
• Với sự kiện loại 2: \(1\le E<N\) và \(1\le X\le10^6\).
• Với sự kiện loại 3: \(1\le V\le N\).

Phân nhóm

1. \(6\) điểm: \(N,Q\le2\,000\).
2. \(7\) điểm: \(A_j=1\), \(B_j=j+1\) với mọi \(1\le j\le N-1\); mọi truy vấn loại 3 hỏi thành phố \(1\).
3. \(14\) điểm: \(N-1\) chia hết cho \(3\). Đặt \(m=(N-1)/3\). Với mọi \(j=1,\ldots,N-1\):

Mọi truy vấn loại `3` đều có $V_k=1$.

1. \(25\) điểm: không có sự kiện loại 1; mọi truy vấn loại 3 hỏi thành phố \(1\).
2. \(12\) điểm: mọi truy vấn loại 3 hỏi thành phố \(1\).
3. \(22\) điểm: không có sự kiện loại 1.
4. \(14\) điểm: không có ràng buộc thêm.

Ví dụ

7
1 2 30
2 3 30
1 4 70
2 5 20
1 6 10
2 7 50
2
3
0
0
0
1
0
8
3 1
1 6 0
3 1
2 6 10
3 1
1 2 7
1 6 7
3 1

80
70
60
-1

6
1 2 10
1 3 30
1 4 50
1 5 30
1 6 10
2
0
0
0
0
1
10
3 1
2 3 20
3 1
1 6 0
3 1
1 1 4
3 1
1 2 6
1 3 6
3 1

30
20
10
30
-1

Nguồn

JOI 2025/2026 - Chung kết, Cuộc thi 4, bài Festivals in JOI Kingdom 3.

Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.