JOI Open Contest 2014 - Ngày 1

Trong Vương quốc IOI có \(N\) thành phố, được đánh số từ \(0\) đến \(N-1\). Các thành phố được nối bởi \(N-1\) con đường hai chiều, và có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác.

Vương quốc có nhiều công ty sản xuất linh kiện đặc biệt. Mỗi công ty chỉ sản xuất một loại linh kiện, và không có hai công ty nào sản xuất cùng một loại. Mỗi công ty có ít nhất một nhà máy; mỗi nhà máy nằm tại một thành phố, và một thành phố có thể có nhà máy của nhiều công ty.

Đôi khi một công ty cần linh kiện của một công ty khác. Nếu công ty \(C_A\) cần linh kiện của công ty \(C_B\) với \(C_A \ne C_B\), linh kiện có thể được vận chuyển từ bất kỳ nhà máy nào của \(C_B\) đến bất kỳ nhà máy nào của \(C_A\). Hai nhà máy được chọn sao cho khoảng cách vận chuyển là nhỏ nhất.

Cho cây đường của vương quốc và \(Q\) truy vấn. Trong truy vấn thứ \(j\), công ty \(U_j\) có nhà máy tại các thành phố \(X_{j,0},\ldots,X_{j,S_j-1}\) cần linh kiện của công ty \(V_j\) có nhà máy tại các thành phố \(Y_{j,0},\ldots,Y_{j,T_j-1}\). Với mỗi truy vấn, hãy trả về khoảng cách vận chuyển nhỏ nhất.

Chi tiết cài đặt

Bài nộp phải khai báo:

#include "factories.h"

và cài đặt chính xác hai hàm sau:

void Init(int N, int A[], int B[], int D[]);
long long Query(int S, int X[], int T, int Y[]);

Hàm Init được gọi đúng một lần lúc bắt đầu.

• N là số thành phố.
• A, B, D là các mảng độ dài \(N-1\).
• Với mỗi \(0 \le i \le N-2\), có một con đường độ dài D[i] nối A[i] và B[i].

Hàm Query được gọi một lần cho mỗi truy vấn.

• S và T lần lượt là số thành phố có nhà máy của hai công ty.
• X là mảng độ dài S chứa các thành phố có nhà máy của công ty cần nhận linh kiện.
• Y là mảng độ dài T chứa các thành phố có nhà máy của công ty cung cấp linh kiện.
• Hàm phải trả về khoảng cách nhỏ nhất giữa một thành phố trong X và một thành phố trong Y.

Bài nộp không được cài đặt hàm main.

Định dạng bộ chấm mẫu

Bộ chấm mẫu đọc:

• Dòng đầu gồm \(N,Q\).
• \(N-1\) dòng tiếp theo, dòng thứ \(i+1\) gồm \(A_i,B_i,D_i\).
• Mỗi truy vấn gồm ba dòng: dòng đầu chứa \(S_j,T_j\); dòng sau chứa \(S_j\) số \(X_{j,0},\ldots,X_{j,S_j-1}\); dòng cuối chứa \(T_j\) số \(Y_{j,0},\ldots,Y_{j,T_j-1}\).

Bộ chấm mẫu in giá trị trả về bởi từng lời gọi Query, mỗi giá trị trên một dòng.

Ràng buộc

• \(2 \le N \le 500\,000\).
• \(1 \le Q \le 100\,000\).
• \(0 \le A_i,B_i \le N-1\) và \(A_i \ne B_i\).
• \(1 \le D_i \le 100\,000\,000\).
• Các con đường nối mọi thành phố thành một cây.
• \(1 \le S_j,T_j \le N-1\).
• Mọi phần tử của X và Y nằm trong đoạn \([0,N-1]\).
• Trong mỗi truy vấn, tất cả thành phố xuất hiện trong X và Y đôi một khác nhau.

Phân nhóm

• Nhóm 1 (15 điểm): \(N,Q \le 5\,000\)
• Nhóm 2 (18 điểm): \(S_j,T_j \le 10\) với mọi truy vấn
• Nhóm 3 (67 điểm): Không có ràng buộc bổ sung

Ví dụ

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

12
3
11

Giáo sư K dùng \(N\) lá bài để bói kết quả của đoàn Nhật Bản tại IOI. Hai mặt của lá bài thứ \(i\) lần lượt ghi các số nguyên \(A_i\) và \(B_i\); hai số này không nhất thiết bằng nhau.

Ban đầu, tất cả lá bài được đặt sao cho mặt ghi \(A_i\) hướng lên. Sau đó, với mỗi \(j=1,2,\ldots,K\), giáo sư thực hiện thao tác sau: lật mọi lá bài có số đang hiện không lớn hơn \(T_j\).

Kết quả bói toán là tổng các số hiện trên bàn sau khi hoàn thành cả \(K\) thao tác. Hãy tính kết quả đó.

Dữ liệu vào

• Dòng đầu gồm hai số nguyên \(N,K\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) gồm \(A_i,B_i\).
• \(K\) dòng tiếp theo, dòng thứ \(j\) chứa \(T_j\).

Dữ liệu ra

In ra tổng các số hiện trên các lá bài sau khi hoàn thành mọi thao tác.

Ràng buộc

• \(1 \le N,K \le 200\,000\).
• \(1 \le A_i,B_i \le 1\,000\,000\,000\).
• \(1 \le T_j \le 1\,000\,000\,000\).

Phân nhóm

• Nhóm 1 (4 điểm): \(N,K \le 1\,000\)
• Nhóm 2 (31 điểm): \(N,K \le 40\,000\)
• Nhóm 3 (65 điểm): Không có ràng buộc bổ sung

Ví dụ

5 3
4 6
9 1
8 8
4 2
3 7
8
2
9

18

Trong một thiên hà xa xôi có \(N\) hành tinh, được đánh số từ \(1\) đến \(N\). Mỗi hành tinh có đúng một máy dịch chuyển với đích đến cố định, và máy dịch chuyển chỉ hoạt động theo một chiều.

Triển lãm hiện tại của Bảo tàng Nghệ thuật Đế quốc Thiên hà được tổ chức tại hành tinh \(1\). Triển lãm tiếp theo sẽ được tổ chức tại hành tinh đạt được sau khi dùng máy dịch chuyển đúng \(K\) lần, bắt đầu từ hành tinh \(1\).

Một tên cướp không gian sẽ xâm nhập hệ thống của đúng một hành tinh \(a\) và ghi đè đích đến của máy dịch chuyển tại đó thành hành tinh \(b\). Cảnh sát không biết cụ thể \(a\) và \(b\).

Với mỗi hành tinh \(i\), hãy tính số cặp có thứ tự \((a,b)\) sao cho sau thay đổi này, triển lãm tiếp theo được tổ chức tại hành tinh \(i\).

Dữ liệu vào

• Dòng đầu gồm hai số nguyên \(N,K\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(A_i\), là đích đến hiện tại của máy dịch chuyển tại hành tinh \(i\).

Dữ liệu ra

In \(N\) dòng. Dòng thứ \(i\) chứa số cặp \((a,b)\) khiến hành tinh đạt được sau đúng \(K\) lần dịch chuyển từ hành tinh \(1\) là \(i\).

Lưu ý

• Có thể có \(A_i=i\).
• Có thể chọn \(b=A_a\), tức là thao tác ghi đè không làm thay đổi đích đến. Những cặp như vậy vẫn phải được tính.
• Những cặp có \(a=b\) cũng phải được tính.

Ràng buộc

• \(1 \le N \le 100\,000\).
• \(N \le K \le 10^{18}\).
• \(1 \le A_i \le N\).

Phân nhóm

• Nhóm 1 (10 điểm): \(N \le 100\)
• Nhóm 2 (37 điểm): \(N \le 3\,000\)
• Nhóm 3 (33 điểm): Các giá trị \(A_i\) đôi một khác nhau
• Nhóm 4 (20 điểm): Không có ràng buộc bổ sung

Ví dụ

5 7
5
1
4
3
2

1
2
3
3
16

40 57
9
24
1
28
29
5
9
1
36
5
35
14
14
29
28
34
28
4
34
36
33
11
22
23
10
18
26
33
36
15
37
31
27
16
25
37
6
31
21
31

4
2
1
12
18
9
1
1
15
0
4
0
0
2
0
11
0
12
0
2
0
0
1
0
5
12
13
13
34
0
5
1
15
10
8
1351
36
1
0
1