LQDOJ Contest #6

Mùa đông lạnh lẽo đã tới rồi. Chúng mình xin được chúc tất cả các bạn nam đang làm contest này sẽ có người yêu, đừng như shiba trong chuỗi bài này nhé!

Nổi danh đã lâu trong giới lập trình thi đấu nhưng mà là "ao hồ", Trần Thanh Nguyên - còn được biết đến với shiba - là một chàng trai với cơ bụng sáu múi, cao mét tám. Có thể nói là mẫu chồng quốc dân của chị em. À đó là Trần Thanh Nguyên nào chứ shiba này là một chàng trai học công nghệ thông tin bình thường. Trước kia, cậu ấy có một cô bạn gái cực kì xinh gái, nhưng đã không giữ được cô ấy do không thực sự xuất sắc lắm ~nói thẳng ra là do lúc đó anh ta quá nghèo~. Giờ đây đã khác, tuy shiba có tất cả, nhưng giống như lời bài hát nào đó, "chúng ta sau này, chẳng có chúng ta sau này", có tất cả nhưng lại không có em. Chính vì vậy, cậu ấy rất nặng tình với "người yêu cũ" của mình, đó là cậu ấy nói vậy, còn người đời như _minhduc hay Flower_On_Stone thì lại cho là "luỵ", "nhớ" người yêu cũ.

Ngày \(19/11\) năm nay, shiba không có ai chúc mừng ngày Quốc tế Đàn ông, cậu ấy lại nhớ ngày xửa ngày xưa, người ấy đã chúc cậu ấy ngày \(19/11\) vui vẻ như thế nào. Và cậu nhớ lại kỉ niệm với cô ấy. Để hồi tưởng lại, cậu ấy quyết định hồi tưởng từ ngày bắt đầu tán cô ấy.

shiba đã chọn cách tán gái mà đa phần các chàng trai hay làm, đó là tặng sữa Milo cho cô bạn kia. Để nhắc mình nhớ về ngày hôm ấy có tặng cô bạn của mình sữa hay không, cậu ấy sẽ ghi số \(1\) hoặc \(0\) vào nhật kí của mình, biểu diễn cho ngày hôm ấy cậu ấy có hay không mua sữa cho cô bạn của mình. Lâu dần, việc này đã biến cuốn nhật kí của shiba thành một xâu nhị phân \(s\). Việc tán cô bạn đã tốn mất \(n\) ngày của shiba, nên xâu nhị phân đó có độ dài là \(n\).

Giờ đây, chỉ còn mình shiba ngồi lại, cậu ấy nhớ lại những kỉ niệm mua sữa cho cô ấy, và cậu ấy nhận thấy, không biết có phải trùng hợp ngẫu nhiên hay không, nếu như từ ngày \(l\) tới ngày \(r\) (\(l \le r\)), biểu diễn thập phân của đoạn đó đúng bằng \(r-l+1\) thì cô ấy sẽ cực kì vui vẻ và cậu ấy coi đây là một quãng đẹp. Nói cách khác, gọi \(f(l,r)\) là giá trị một số nguyên biểu diễn dưới dạng xâu nhị phân của xâu \(S\) được cắt ra từ vị trí \(l\) đến \(r\) của xâu \(s\), nếu \(f(l,r) = r-l+1\) thì đây sẽ được coi là một quãng đẹp. Cậu ấy tự hỏi, quãng thời gian đó, cô ấy đã vui vẻ được bao nhiêu lần, cậu ấy đã tạo ra được bao nhiêu quãng đẹp. Các quãng đẹp nếu đè lên nhau hoặc chứa nhau vẫn được coi là hai quãng đẹp riêng biệt.

Yêu cầu: Tính số quãng đẹp mà shiba đã tạo ra.

Input

• Dòng đầu tiên chứa một số nguyên \(\phi\) - số thứ tự của subtask chứa test đó.
• Dòng thứ hai chứa một số nguyên dương \(n\) (\(n \le 5 \times 10^5\)).
• Dòng thứ ba chứa một xâu nhị phân \(s\) độ dài \(n\).

Output

• Một dòng chứa một số nguyên là kết quả bài toán.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): xâu \(s\) chỉ chứa một loại kí tự.
• Subtask \(2\) (\(10\%\) số điểm): \(n \le 50\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 10^3\).
• Subtask \(4\) (\(15\%\) số điểm): xâu được tạo thành từ một xâu con lặp lại nhiều lần, độ dài xâu con đó không vượt quá \(30\) (*).
• Subtask \(5\) (\(20\%\) số điểm): \(n \le 10^4\).
• Subtask \(6\) (\(25\%\) số điểm): không có ràng buộc gì thêm.

Example

2
4
0110

4

Sau khi nhớ về khoảng thời gian đẹp đẽ ấy, shiba lại nhớ lại không gian lãng mạn lúc hai người gặp nhau. Có không gian thì phải có thời gian chứ, đúng không?..."

Do quá nhớ cô ấy, shiba quyết định sẽ đi tìm lại cô ấy ở ngoài đời để trực tiếp nói chuyện. Cách nhanh nhất là tìm đến nhà cô ấy. Cũng may, cô ấy block hết mạng xã hội nhưng không chặn số điện thoại. May mắn hơn nữa là shiba đã gọi điện được cho cô ấy hẹn cô ấy đi chơi và được cô ấy đồng ý.

Quãng thời gian yêu nhau, shiba không biết bao nhiêu lần đi đến nhà cô ấy nên đã thuộc địa chỉ nhà cô ấy ở đâu. Coi thành phố nơi shiba và cô ấy đang sống là một mặt phẳng toạ độ, nhà của shiba ở toạ độ \((1,1)\) còn nhà cô ấy ở toạ độ \((n,m)\). Mỗi bước di chuyển, shiba có thể đi trái, đi phải, đi lên hoặc đi xuống (không được đi chéo).

Do quãng thời gian đó, shiba chỉ lo đi chơi với cô ấy, nên không nhớ được đoạn đường ngắn nhất đến nhà cô ấy. Để tiết kiệm chi phí nhiên liệu, cậu ấy cần tìm độ dài của đường đi ngắn nhất tới nhà cô ấy. Hơn nữa, shiba cũng lo có thể sẽ tắc đường làm ảnh hưởng tới chuyện "quan trọng" này của cậu ấy, nên cậu ấy muốn tìm thêm vài con đường cũng có độ dài ngắn nhất như thế. Tuy nhiên cậu ấy đang mải chọn quà với tương tư người ấy nên không thể làm được chuyện "đơn giản" này, nên cậu ấy đã nhờ _minhduc mang chiếc MacBook M2 Pro đi tính hộ. Ngặt nỗi lúc đó _minhduc cũng đang bận một vài chuyện nên không thể làm được chuyện này.

Yêu cầu: Giả sử bạn là bạn thân của _minhduc, được _minhduc chỉ rõ mọi đường từ nhà của shiba tới nhà cô ấy và bạn được _minhduc nhờ ~với vài cái phong bì~. Hãy tính giúp _minhduc đường đi ngắn nhất và số đường đi có độ dài như thế. Do độ dài đường đi ngắn nhất và số lượng đường đi có thể rất lớn, bạn cần in ra chúng sau khi chia lấy dư cho \(10^9+7\).

Input

• Chứa hai số nguyên dương lần lượt là \(n\) và \(m\) (\(1 \le n,m \le 5 \times 10^7\)).

Output

• In ra lần lượt là độ dài đường đi ngắn nhất và số đường đi có độ dài như vậy, cả hai số cần được in ra sau khi chia lấy dư cho \(10^9+7\).

Scoring

• Subtask \(1\) (\(10\%\) số điểm): Có \(n,m \le 10\).
• Subtask \(2\) (\(30\%\) số điểm): Có \(n,m \le 1000\).
• Subtask \(3\) (\(20\%\) số điểm): Có \(n \times m \le 10^7\).
• Subtask \(4\) (\(20\%\) số điểm): Có \(n,m \le 10^7\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

2 3

4 3

5 7

11 210

Sau khi tìm được đường đi ngắn nhất tới nhà cô "bạn gái cũ", shiba đã quyết định sẽ cùng cô ấy đi du lịch khắp đất nước để tìm cảm giác mới mẻ cũng như hàn gắn tình cảm. Chuyến du lịch ấy liệu có thành công mĩ mãn, hay sẽ đầy những trắc trở trông gai...

Sau khi hẹn được cô bạn gái đi chơi du lịch dài ngày, shiba quyết định sẽ đi du lịch bằng xe máy và chở cô ấy đi, tất nhiên là sẽ tiện hơn đi taxi vì cậu ấy có thể dừng lại có bất cứ đâu cậu ấy muốn để ngắm cảnh, mà lúc đi xe được cô ấy ôm thì lại còn gì tuyệt vời bằng, đúng không nhỉ :3.

Có thể coi đất nước nơi shiba sống là một đồ thị vô hướng có trọng số. Đất nước nơi shiba đang sống rất rộng lớn và được chia làm \(n\) thành phố. Có tất cả \(m\) đường nối giữa các thành phố với nhau, trong đó giữa hai thành phố có thể có nhiều hơn một đường nối và tồn tại đường đi từ một thành phố tới chính nó. Mỗi đường nối sẽ nối thành phố \(u_i\) và \(v_i\) với nhau và có trọng số bằng \(c_i\).

shiba thắc mắc, nếu như hôm nay mình chọn xe có mức đốt năng lượng là \(g\), thì cậu ấy có thể di chuyển được giữa bao nhiêu cặp thành phố khác nhau với nhau. Biết rằng trọng số của một đường đi là trọng số của cạnh lớn nhất trên đường đi đó. Để di chuyển được trên một đường đi, chiếc xe của shiba cần có mức đốt năng lượng lớn hơn hoặc bằng trọng số của đường đi đó.

Do đang bận soạn đồ, shiba không tính được điều này, thế nên vấn đề này được gửi tới _minhduc và hội bạn của cậu ấy - những Quân Sư uy tín. Do cũng đang mải bận tư vấn tình cảm, _minhduc quyết định sẽ đưa bài tập này lên LQDOJ Contest #6, các bạn hãy thử sức nhé.

Đang kích 4 Quân Sư rồi, sao bạn không thử để có thể kích 5 Quân Sư, tăng độ tự tin cho shiba nhỉ :Đ

Yêu cầu: Với mỗi truy vấn là một lần chọn xe, hãy đưa ra số lượng đường đi thoả mãn.

Input

• Dòng đầu tiên chứa một số nguyên \(\phi\) - số thứ tự của subtask chứa test đó.
• Dòng thứ hai chứa hai số nguyên \(n,m\) (\(1 \le n \le 3 \times 10^5, 1 \le m \le 5 \times 10^5\)).
• \(m\) dòng tiếp theo chứa ba số nguyên \(u_i,v_i,c_i\) (\(1 \le u_i, v_i \le n, 1 \le c_i \le 10^5\)).
• Dòng tiếp theo chứa một số nguyên dương \(q\) - số lượng truy vấn (\(1\le q \le 3 \times 10^5\)).
• Dòng cuối cùng chứa \(q\) số nguyên, lần lượt là các truy vấn (\(1 \le g \le 10^9\)).

Output

• In ra gồm \(q\) dòng, mỗi dòng chứa một số nguyên, là kết quả của truy vấn.

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(n \le 100, q \le 100, m = n-1\).
• Subtask \(2\) (\(15\%\) số điểm): \(n \le 100, q \le 100\).
• Subtask \(3\) (\(10\%\) số điểm): \(m = n-1\), cạnh thứ \(i\) nối hai thành phố \(i\) và \(i+1\).
• Subtask \(4\) (\(10\%\) số điểm): \(m = n-1\), mỗi thành phố có tối đa \(2\) con đường nối tới nó.
• Subtask \(5\) (\(15\%\) số điểm): \(n \le 10^3\).
• Subtask \(6\) (\(15\%\) số điểm): \(m = n-1\).
• Subtask \(7\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

1
3 2
2 3 1
1 3 2
7
1 4 1 2 1 1 3

1
3
1
3
1
1
3

Quãng đường đi du lịch rất vui vẻ, nhưng đã gặp một vài biến cố...

Trên đường đi chơi quanh đất nước, cô "bạn gái" của shiba bỗng hướng ánh mắt vào một tiệm gấu nhồi bông. Để có thể lấy được gấu nhồi bông cho cô ấy, shiba quyết định sẽ chơi ném phi tiêu để nhận phần thưởng. Bằng kĩ năng "aim" "bách phát bách trượt" của mình, tất nhiên là cậu ấy không trúng phát nào rồi. Tuy nhiên, cô chủ tiệm gấu nhồi bông lại là một người đam mê tin học. Nhận ra dáng vẻ của một "lập trình viên" - ~lưng gù, trán có nếp nhăn, mặt già~ đẹp trai phong độ ngời ngợi tới từ shiba, cô chủ quyết định nhờ cậu ấy giải một bài toán, và hứa sẽ tặng tất cả gấu nhồi bông nếu cậu ấy giải được bài toán này. Bài toán đó như sau:

Cho một mảng \(a\) có \(n\) phần tử \(a_1,a_2,...,a_n\). Có hai loại truy vấn như sau:

• 1 p x: Gán giá trị cho phần tử \(a_1\) bằng \(x\).
• 2: Dựng \(n\) dãy:
  • Với \(i = 1\): \(b_{i,k} = a_k\), \(S = S + b_{i,k}\).
  • Với \(i > 1\): \(b_{i,k} = b_{i-1,k}\) \(\text AND\) \(b_{i-1,k+1}\), \(S = S + b_{i,k}\).

Do đang mải đi chơi, shiba quyết định gửi gắm bài toán này tới các bạn. Để shiba có thể quay lại với "người yêu cũ", sao các bạn không góp ~một chân~ một tay cho cậu ấy nhỉ?

Yêu cầu: Với mỗi thao tác loại \(2\), in ra kết quả của số \(S\).

Biểu thức \(x\) \(AND\) \(y\) biểu diễn phép toán tử AND của hai số \(x\) và \(y\).

Input

• Dòng thứ nhất chứa một số nguyên \(\phi\) - số thứ tự của subtask chứa test đó.
• Dòng thứ hai chứa một số nguyên dương \(n\) (\(1 \le n \le 10^5\)).
• Dòng thứ ba chứa \(n\) số nguyên \(a_1, a_2,..., a_n\) (\(0 \le a_i \le 10^5\)).
• Dòng thứ tư chứa một số nguyên \(q\) (\(q \le 10^5\)) - số lượng truy vấn.
• \(q\) dòng tiếp theo, mỗi dòng chứa một truy vấn thuộc một trong hai dạng như trên, truy vấn dạng 1 p x có \(1 \le p \le n, 0 \le x \le 10^5\).

Output

• Với mỗi truy vấn loại \(2\), in ra kết quả bài toán trên một dòng.

Scoring

Gọi \(query\) là số lượng truy vấn loại \(2\).

• Subtask \(1\) (\(10\%\) số điểm): \(q = 1\), \(query = 1\), \(a_1 = a_2 = ... = a_n = 0\),
• Subtask \(2\) (\(25\%\) số điểm): \(n \le 100, q \le 100\).
• Subtask \(3\) (\(15\%\) số điểm): \(q = 1\), \(query = 1\), \(a_1 = a_2 = ... = a_n\).
• Subtask \(4\) (\(20\%\) số điểm): \(query <= 10\).
• Subtask \(5\) (\(30\%\) số điểm): không có ràng buộc gì thêm.

Example

2
3
1 1 1
6
2
1 2 2
2
1 3 2
1 1 2
2

6
4
12

Sau khi trở về từ chuyến đi chơi, shiba vẫn bị cô ấy từ chối quay lại, đã thế lại còn yêu thằng khác giàu ngang shiba thậm chí còn đẹp trai hơn shiba ~cụ thể là yêu _minhduc~. Do quá cay cú, shiba thề sẽ phải cố gắng thành lập công ti giàu nhất Việt Nam để trả thù cho cô "người yêu cũ" phải hối hận. Hai năm sau, shiba đã trở thành CEO của một công ty lớn nhất Việt Nam như anh ấy đã thề, nhưng hiện nay công ty lại có một vấn đề "nho nhỏ"...

shiba là CEO của một công ty với \(N\) nhân viên, đánh số từ \(1\) đến \(N\). Hệ thống tổ chức của công ty được phân theo các cấp bậc – mọi nhân viên, trừ nhân viên đánh số \(1\) thì mọi nhân viên đều có đúng một cấp trên trực tiếp. Nói cách khác, mọi nhân viên đều có \(1\) hoặc nhiều cấp dưới (trực tiếp hoặc gián tiếp) bao gồm cả chính nhân viên đó. Ví dụ, nhân viên đánh số \(1\) sẽ có chính xác \(N\) cấp dưới. Với mỗi nhân viên \(X\), ta gọi \(X\) là cấp dưới mức độ \(0\). Tiếp đó, các cấp dưới trực tiếp của nhân viên ấy sẽ gọi là cấp dưới mức độ \(1\). Và mọi cấp dưới trực tiếp của các nhân viên ấy (những nhân viên mà là cấp dưới trực tiếp của \(X\)) sẽ gọi là cấp dưới mức độ \(2\). Cách gọi này tương tự với các cấp dưới nữa.

Có một thông tin quan trọng mà một số nhân viên đã biết từ trước ~tin đó là cô người yêu cũ của shiba sắp cưới với _minhduc nhưng lại đang có bồ nhí ở ngoài~, và shiba muốn cả công ty cùng biết đến. Nhiều lần, shiba sẽ chọn ra nhân viên \(X\) và một giá trị nguyên \(K\), sau đó shiba sẽ chia sẻ thông tin này cho các cấp dưới từ mức độ \(0\) đến mức độ \(K\) (nếu mức độ của cấp dưới của \(X\) cao nhất mà nhỏ hơn \(K\) thì ta chỉ xét đến đấy). Để cho đơn giản, ta sẽ gọi các cấp dưới này là “cấp dưới \(K\)”. Vấn đề của cách làm này là trong nhiều trường hợp, sẽ có nhiều nhân viên đã biết từ trước về thông tin cần chia sẻ, điều này có thể gây lãng phí thời gian và tài nguyên của công ty. Do đó shiba muốn tính xem với các nhân viên \(X\) cần xét, số cấp dưới \(K\) của nhân viên \(X\) mà đã biết tin tức này là bao nhiêu.

Yêu cầu: Vì số lượng nhân viên quá lớn nên shiba không thể tính một cách thủ công được. Anh ta muốn viết một chương trình để tính, nhưng làm CEO đã lâu nên shiba không còn nhớ cách code. Bạn hãy giúp anh ấy lập chương trình để tính toán theo ý muốn của shiba.

~tin chấn động như thế các bạn hãy giúp shiba tính để anh ta còn rủ nhân viên của mình đi hóng drama _minhduc bắt quả tang ngay trong đám cưới của cô người yêu cũ đi chứ :Đ~

Input

• Dòng đầu tiên chứa số nguyên \(N\) – số lượng nhân viên trong công ty của shiba \((2 \le N \le 2 \times 10^5)\).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x\) và \(y\) cho biết quan hệ giữa các nhân viên, cụ thể là nhân viên \(x\) sẽ là cấp trên trực tiếp của nhân viên \(y\)
• Dòng tiếp theo chứa \(N\) số nguyên nguyên: \(b_1, b_2, ..., b_N\) với hai giá trị là \(0\) hoặc \(1\), cho biết nhân viên thứ \(i\) có biết thông tin cần chia sẻ này từ trước hay không (ở đây \(1\) mang nghĩa là biết và \(0\) là không).
• Dòng tiếp theo chứa một số nguyên dương \(Q\) – số truy vấn \((1 \le Q \le 2 \times 10^5)\).
• \(Q\) dòng cuối cùng của bộ dữ liệu sẽ là các truy vấn của bài. Truy vấn gồm \(2\) loại gồm:
  • Loại \(1\) (chia sẻ thông tin): 1 x k: shiba thông báo thông tin tới tất cả cấp dưới \(K\) của nhân viên \(X\) \((0 \le K \le N)\).
  • Loại \(2\) (xác định số lượng): 2 x k: shiba muốn xác định có bao nhiêu cấp dưới \(K\) của nhân viên \(X\) đã biết thông tin cần chia sẻ \((0 \le K \le N)\).

Output

• Với mỗi truy vấn loại \(2\), in ra một dòng là đáp án theo thứ tự của input.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): Có \(N\le{10}^4,\ Q\le{10}^4\).
• Subtask \(2\) (\(20\%\) số điểm): Có \(k=N\) trong mọi truy vấn.
• Subtask \(3\) (\(20\%\) số điểm): Có tất cả các truy vấn là truy vấn loại \(2\).
• Subtask \(4\) (\(20\%\) số điểm): Có \(N\le{5\times10}^4,\ Q\le{5\times10}^4\).
• Subtask \(5\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

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

1
3
0
6
3
4
6