Bài tập

Trên trục số, bạn được cho \(N\) đoạn thẳng \([L_1; R_1], [L_2; R_2], \ldots, [L_N; R_N]\) với tọa độ đầu mút là các số nguyên dương.

Một thao tác chia nhỏ sẽ thay thế đoạn thẳng \([L; R]\) bằng hai đoạn \([L; M]\) và \([M; R]\), trong đó \(M\) là một số nguyên dương và \(L < M < R\). Bạn có thể chia cả những đoạn ban đầu lẫn những đoạn mới sinh ra sau các lần chia trước đó.

Ta nói đoạn thẳng \([A; B]\), trong đó \(A < B\) và \(A, B\) là các số nguyên dương, phù mạnh đoạn \([L; R]\) nếu đoạn \([A; B]\) bao phủ ít nhất một nửa độ dài của đoạn \([L; R]\).

Yêu cầu: Tìm độ dài ngắn nhất có thể của một đoạn thẳng \([A; B]\) sao cho sau khi thực hiện chính xác \(K\) thao tác chia nhỏ, đoạn \([A; B]\) phủ mạnh tất cả \(N + K\) đoạn thẳng cuối cùng.

Input

Vào từ tệp văn bản SEGCOV.INP:

• Dòng đầu chứa hai số nguyên \(N\) và \(K\) \((1 \le N \le 10^5,\ 0 \le K \le 10^{14})\);
• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L_i\) và \(R_i\) \((1 \le L_i < R_i \le 10^9)\), biểu diễn đoạn thẳng thứ \(i\).

Biết rằng, luôn tồn tại \(K\) thao tác chia nhỏ từ các đoạn đã cho và một số đoạn đầu vào có thể trùng nhau hoàn toàn.

Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.

Output

Ghi ra tệp văn bản SEGCOV.OUT một số nguyên duy nhất là độ dài nhỏ nhất có thể của đoạn thẳng \([A; B]\) sao cho \([A; B]\) phù mạnh tất cả các đoạn cuối cùng nhận được sau \(K\) thao tác chia nhỏ.

Example

3 3
1 7
3 8
2 9

4

6 15
4 10
2 8
7 14
1 9
5 12
3 13

7

Scoring

• Subtask 1 (15% số điểm): \(K = 0\);
• Subtask 2 (15% số điểm): không có hai đoạn thẳng nào giao nhau;
• Subtask 3 (10% số điểm): \(N \le 500\), \(R_i \le 500\);
• Subtask 4 (20% số điểm): \(N \le 5000\), \(R_i \le 5000\);
• Subtask 5 (20% số điểm): \(N \le 10^4\);
• Subtask 6 (20% số điểm): không có ràng buộc gì thêm.

Ở một thiên hà xa xôi, nơi mà vị thần Eros cai quản đang tổ chức một đại hội thể thao quy mô toàn thiên hà. Cư dân trên tất cả các hành tinh đều có thể đăng ký tham gia. Thần Eros là người đứng ra chỉ huy và tổ chức đại hội diễn ra vào tháng sau. Để kì đại hội trở nên công bằng đối với tất cả mọi người, thần Eros quyết định ngăn chặn những hành tinh có thể gian lận với nhau. Thiên hà bao gồm \(N\) hành tinh và \(N-1\) con đường nối các hành tinh lại với nhau tạo thành một đồ thị dạng cây. Con đường thứ \(i\) kết nối trực tiếp hành tinh \(u_i\) với hành tinh \(v_i\) và trọng số của con đường này là \(w_i\). Một hành tinh có thể đến được bất kỳ hành tinh nào khác thông qua một số con đường. Chiều dài đường đi giữa 2 hành tinh bằng tổng \(xor\) trọng số của các con đường trên đường đi giữa 2 hành tinh đó.

Hai hành tinh có thể là 1 cặp gian lận với nhau nếu như độ dài đường đi giữa chúng bằng 0. Vì để tránh sự gian lận nên thần Eros quyết định sử dụng thần lực phá hủy lần lượt các con đường theo một thứ tự nhất định. Thần Eros quan tâm rằng sau khi mình phá hủy một con đường thì còn bao nhiêu cặp hành tinh có thể gian lận với nhau ?

Yêu cầu: Hãy giúp thần Eros xác minh điều đó.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) (\(N\leq 100000\)).

• Dòng thứ \(i\) trong số \(N-1\) dòng tiếp theo chứa 3 số nguyên \(u_i,v_i,w_i\) (\(1\leq u_i\leq v_i\leq N,0\leq w_i\leq 10^9\)) mô tả con đường thứ \(i\).

• Dòng tiếp theo chứa \(N-1\) số nguyên \(x_1,x_2,…,x_{N-1}\) thể hiện thứ tự phá huỷ các con đường. Số nguyên thứ \(i\) cho biết thần Eros sẽ phá hủy con đường thứ \(x_i\).

Output

• Gồm \(N\) dòng, dòng thứ \(i\) chứa một số nguyên là số cặp hành tinh có thể gian lận sau khi đã phá hủy \(i-1\) con đường theo thứ tự trên.

Example

3
1 2 4
2 3 4
1 2

1
0
0

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N\leq 1000\).

• Subtask \(2\) (\(30\%\) số điểm): \(w_1=w_2=\ldots=w_{N-1}=0\).

Vân có \(N\) đồ trang sức trên kệ được đánh số \(1, 2, ..., N\) từ trái sang phải. Đồ trang sức có nhiều loại khác nhau, được biểu thị bằng số nguyên dương. Món đồ thứ \(i\) trên kệ là loại \(A_i\).

Hôm nay Vân sẽ bay ra nước ngoài gặp gia đình và muốn mang theo càng nhiều đồ trang sức càng tốt. Tuy nhiên, vì đang vội nên Vân phải lấy một khoảng đồ trang sức liên tiếp trên kệ. Nghĩa là Vân sẽ chọn hai chỉ số, \(l\) và \(r\), và lấy tất cả các món đồ trang sức được đánh số \(l, l+1, ..., r-1, r\). Ngoài ra, do các quy tắc về thuế, an ninh sân bay sẽ vứt bỏ tất cả các loại đồ trang sức mà Vân có nhiều hơn \(S\) món trong loại đó mang theo.

Ví dụ: giả sử \(S = 2\), Vân mang theo sáu món đồ trang sức: một loại 0, hai loại 1 và ba loại 2. Vân sẽ mất tất cả các nữ trang loại 2 ở sân bay!

Yêu cầu: Hãy giúp Vân chọn \(l\) và \(r\) sao cho cô ấy có thể mang được nhiều đồ trang sức nhất cho gia đình mình.

Input

• Dòng đầu tiên ghi duy nhất một số nguyên \(T\leq 5\) là số lượng trường hợp test. Mỗi nhóm dòng trong số \(T\) nhóm dòng sau bao gồm:

• Dòng một chứa hai số nguyên dương \(N\) và \(S\) (\(S \leq N \leq 10^5\)).

• Dòng thứ hai chứa \(N\) số nguyên dương, số thứ \(i\) là \(A_i\) (\(A_i \leq 10^5\)).

Output

• Ghi ra \(T\) dòng, mỗi dòng ghi một số nguyên là số đồ trang sức tối đa mà Vân có thể mang ra nước ngoài thăm gia đình.

Example

1
6 2
1 1 4 1 4 4

4

Scoring

• Subtask 1: \(N \leq 1000\).

• Subtask 2: \(N \leq 10^5\).

Trong một đất nước có \(N\) thành phố được đánh số từ 1 đến \(N\), các thành phố được nối với nhau bởi \(N - 1\) con đường hai chiều, đảm bảo hai thành phố bất kì có thể đi được đến nhau. Có \(M\) thành phố đang có dịch bệnh. Người ta muốn chọn thành phố để xây dựng bệnh viện dã chiến sao cho: chỉ số an toàn từ thành phố đó đến thành phố đang có dịch bệnh bất kì đều không lớn hơn \(K\) (\(K\) là một số cho trước và chỉ số an toàn giữa hai thành phố \(X\) và \(Y\) được tính bằng tổng số con đường trên đường đi từ \(X\) đến \(Y\)).

Yêu cầu: Em hãy lập trình để tính xem có thể xây dựng bệnh viện dã chiến ở bao nhiêu thành phố?

Input

Vào file văn bản BV.INP:

• Dòng đầu tiên gồm ba số nguyên dương \(N, M, K\) (\(1 \leq K \leq M \leq N \leq 10^5\)) mô tả số lượng thành phố, số lượng thành phố đang có dịch bệnh và số \(K\);
• \(N - 1\) dòng sau gồm hai số nguyên \(u\) và \(v\) mô tả có con đường nối hai thành phố thứ \(u\) và thứ \(v\) (\(1 \leq u, v \leq N\));
• Dòng tiếp theo gồm \(M\) số nguyên \(x\) mô tả những thành phố đang có dịch bệnh (\(1 \leq x \leq N\)).

Output

Ghi ra file văn bản BV.OUT:
Gồm một số nguyên duy nhất là số thành phố có thể thoả mãn đề xây dựng bệnh viện dã chiến (thành phố đang có dịch bệnh cũng có thể xây dựng bệnh viện dã chiến).

Example

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

4

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

2

Scoring

• Có 40% số test ứng với 40% số điểm của bài thoả mãn: \(N \leq 500\);
• 20% số test khác ứng với 20% số điểm của bài thoả mãn: \(N \leq 10^4\);
• 20% số test khác ứng với 20% số điểm của bài thoả mãn: mỗi thành phố chỉ có đường đi trực tiếp đến tối đa hai thành phố khác;
• 20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.