Đất nước IOI có \(N\) thị trấn, được đánh số từ \(0\) đến \(N-1\), và \(N-1\) con đường, được đánh số từ \(0\) đến \(N-2\). Đường \(j\) nối hai chiều thị trấn \(U_j\) và thị trấn \(V_j\). Có thể đi giữa hai thị trấn bất kỳ bằng cách đi qua một số con đường.

Mỗi thị trấn có một nhà hàng. Loại nhà hàng ở thị trấn \(i\) được biểu diễn bởi số nguyên \(F_i\):

• \(F_i=0\): nhà hàng nước ép.
• \(F_i=1\): nhà hàng trứng ốp lết.
• \(F_i=2\): nhà hàng kem.

Rie là hướng dẫn viên du lịch và đang xây dựng chuyến tham quan mang tên JOI Tour, gồm các bước sau:

1. Chọn một thị trấn \(i_0\) có nhà hàng nước ép và bắt đầu chuyến đi tại đó.
2. Ghé nhà hàng nước ép ở thị trấn \(i_0\).
3. Chọn một thị trấn \(i_1\) có nhà hàng trứng ốp lết, rồi đi xe buýt từ \(i_0\) đến \(i_1\) theo đường đi ngắn nhất.
4. Ghé nhà hàng trứng ốp lết ở thị trấn \(i_1\).
5. Chọn một thị trấn \(i_2\) có nhà hàng kem, rồi đi xe buýt từ \(i_1\) đến \(i_2\) theo đường đi ngắn nhất.
6. Ghé nhà hàng kem ở thị trấn \(i_2\).
7. Kết thúc chuyến đi tại thị trấn \(i_2\).

Để khách không cảm thấy nhàm chán, Rie chỉ chọn ba thị trấn sao cho không có con đường nào được đi qua hai lần trong chuyến đi. Một JOI Tour như vậy được gọi là tốt.

Bạn cần tính số bộ ba \((i_0,i_1,i_2)\) thỏa mãn đồng thời các điều kiện:

• Nhà hàng ở \(i_0\) là nhà hàng nước ép.
• Nhà hàng ở \(i_1\) là nhà hàng trứng ốp lết.
• Nhà hàng ở \(i_2\) là nhà hàng kem.
• Khi đi từ \(i_0\) đến \(i_1\), rồi từ \(i_1\) đến \(i_2\), đều theo đường đi ngắn nhất, không con đường nào được đi qua hai lần.

Sẽ có \(Q\) lần thay đổi loại nhà hàng. Trong lần thay đổi thứ \(k+1\) (\(0 \le k \le Q-1\)), bạn được cung cấp hai số nguyên \(X_k,Y_k\). Nhà hàng ở thị trấn \(X_k\) được đổi sang loại \(Y_k\): nước ép nếu \(Y_k=0\), trứng ốp lết nếu \(Y_k=1\), kem nếu \(Y_k=2\). Ngay sau mỗi lần thay đổi, bạn phải cập nhật số JOI Tour tốt và trả kết quả cho Rie.

Chi tiết cài đặt

Bạn cần nộp một tệp tên joitour.cpp. Tệp này phải dùng chỉ thị #include để nạp joitour.h và cài đặt các hàm sau:

void init(int N, std::vector<int> F, std::vector<int> U,
          std::vector<int> V, int Q);
void change(int X, int Y);
long long num_tours();

Hàm init được gọi đúng một lần ở đầu chương trình để cung cấp thông tin ban đầu. Tham số N là số thị trấn, F là mảng có độ dài \(N\) với F[i] là loại nhà hàng ở thị trấn \(i\). Hai mảng U,V có độ dài \(N-1\); U[j],V[j] là hai đầu của đường \(j\). Tham số Q là số lần thay đổi loại nhà hàng.

Hàm change được gọi đúng \(Q\) lần. Trong lần gọi thứ \(k+1\), X là thị trấn \(X_k\) và Y là loại nhà hàng mới \(Y_k\). Loại mới được bảo đảm khác loại hiện tại.

Hàm num_tours được gọi ngay sau init và ngay sau mỗi lần gọi change, tổng cộng \(Q+1\) lần. Mỗi lần gọi phải trả về số JOI Tour tốt ở thời điểm đó.

Bạn được phép cài đặt thêm hàm phụ và khai báo biến toàn cục. Chương trình của bạn không được đọc hoặc ghi qua đầu vào chuẩn, đầu ra chuẩn hay bất kỳ tệp nào. Có thể ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

Chương trình chấm mẫu

Gói tệp được cung cấp chứa chương trình chấm mẫu grader.cpp, tệp khai báo joitour.h, tệp cài đặt mẫu joitour.cpp và compile.sh. Để kiểm tra chương trình, đặt grader.cpp, joitour.cpp và joitour.h trong cùng thư mục và dùng lệnh:

g++ -std=gnu++20 -O2 -o grader grader.cpp joitour.cpp

Cũng có thể chạy compile.sh. Khi biên dịch thành công, tệp thực thi grader được tạo ra. Chương trình chấm thật khác chương trình chấm mẫu. Chương trình chấm mẫu chạy trong một tiến trình, đọc dữ liệu từ đầu vào chuẩn và in kết quả ra đầu ra chuẩn.

Dữ liệu vào

• Dòng đầu chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(F_0,F_1,\ldots,F_{N-1}\).
• Trong \(N-1\) dòng tiếp theo, dòng thứ \(j+1\) chứa hai số nguyên \(U_j,V_j\) (\(0 \le j \le N-2\)).
• Dòng tiếp theo chứa số nguyên \(Q\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(k+1\) chứa hai số nguyên \(X_k,Y_k\) (\(0 \le k \le Q-1\)).

Dữ liệu ra

Sau mỗi lần gọi num_tours, chương trình chấm mẫu in giá trị trả về trên một dòng. Vì vậy, có \(Q+1\) dòng kết quả.

Ràng buộc

• \(3 \le N \le 200000\).
• \(0 \le F_i \le 2\) với mọi \(0 \le i \le N-1\).
• \(0 \le U_j<V_j \le N-1\) với mọi \(0 \le j \le N-2\).
• Có thể đi giữa hai thị trấn bất kỳ bằng cách đi qua các con đường.
• \(0 \le Q \le 50000\).
• \(0 \le X_k \le N-1\) và \(0 \le Y_k \le 2\) với mọi \(0 \le k \le Q-1\).
• Trong mỗi lần gọi change, loại nhà hàng mới khác loại nhà hàng hiện tại.
• Tất cả các giá trị được cung cấp đều là số nguyên.

Phân nhóm

1. \(6\) điểm: \(N \le 400\), \(Q \le 100\).
2. \(8\) điểm: \(N \le 4000\), \(Q \le 1000\).
3. \(6\) điểm: \(Q=0\).
4. \(16\) điểm: \(U_j=j\), \(V_j=j+1\) với mọi \(0 \le j \le N-2\).
5. \(16\) điểm: \(U_j=\lfloor j/2\rfloor\), \(V_j=j+1\) với mọi \(0 \le j \le N-2\).
6. \(34\) điểm: \(N \le 100000\), \(Q \le 25000\).
7. \(14\) điểm: Không có ràng buộc bổ sung.

Ký hiệu \(\lfloor j/2\rfloor\) là số nguyên lớn nhất không vượt quá \(j/2\).

Ví dụ giao tiếp

Ví dụ 1

Dữ liệu vào của trình chấm mẫu:

3
0 1 2
0 1
1 2
0

Dữ liệu ra của trình chấm mẫu:

1

Giải thích

Các lời gọi tương ứng là:

Chỉ có một JOI Tour tốt, ứng với \((i_0,i_1,i_2)=(0,1,2)\). Thị trấn \(0\) có nhà hàng nước ép vì \(F_0=0\); thị trấn \(1\) có nhà hàng trứng ốp lết vì \(F_1=1\); thị trấn \(2\) có nhà hàng kem vì \(F_2=2\). Đi từ \(0\) đến \(1\), rồi từ \(1\) đến \(2\) theo đường đi ngắn nhất không đi qua đường nào hai lần. Vì vậy, lần gọi num_tours đầu tiên trả về \(1\).

Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,2,3,4,6,7\).

Ví dụ 2

Dữ liệu vào của trình chấm mẫu:

3
0 1 2
0 1
1 2
2
2 0
0 2

Dữ liệu ra của trình chấm mẫu:

1
0
1

Giải thích

Các lời gọi tương ứng là:

Ban đầu chỉ có JOI Tour tốt \((0,1,2)\), nên giá trị trả về đầu tiên là \(1\).

Sau lần thay đổi thứ nhất, nhà hàng kem ở thị trấn \(2\) trở thành nhà hàng nước ép. Không còn nhà hàng kem nào, nên không có JOI Tour tốt và giá trị trả về thứ hai là \(0\).

Sau lần thay đổi thứ hai, nhà hàng nước ép ở thị trấn \(0\) trở thành nhà hàng kem. Khi đó có đúng một JOI Tour tốt \((2,1,0)\), nên giá trị trả về thứ ba là \(1\).

Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,2,4,6,7\).

Ví dụ 3

Dữ liệu vào của trình chấm mẫu:

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

Dữ liệu ra của trình chấm mẫu:

3
0
4
4
0
4
5
5

Giải thích

Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,2,5,6,7\).

Giới hạn

Giới hạn thời gian là \(3\) giây; giới hạn bộ nhớ là \(1024\) MB.

Nguồn

Đề bài của Ủy ban Olympic Tin học Nhật Bản, JOI 2023/2024, vòng tuyển chọn mùa xuân, ngày thi thứ ba. Đề gốc và bản dịch tiếng Việt được cung cấp theo giấy phép CC BY-SA 4.0.