USACO 2023 - US Open - Hạng Bạch Kim

Note: Giới hạn thời gian của bài này là 4s, gấp đôi so với thông thường. Bộ nhớ là 512MB, gấp đôi so với thông thường

Pareidolia là một hội chứng mà mắt bạn có xu hướng nhìn thấy những thứ quen thuộc trong ảnh mà thậm chí không tồn tại (ví dụ như thấy một gương mặt trên đám mây). Nông dân John, một người với niềm yêu thương những chú bò của mình, thường xuyên thấy những thứ liên quan đến bò trong mọi vật dụng. Ví dụ, nếu như bác John thấy xâu "bqessiyexbesszieb", đôi mắt của bác sẽ tự động bỏ đi một số kí tự và nhầm lẫn thành "bessiexbessieb" - một xâu gồm \(2\) xâu con liên tiếp "bessie" (tên một cô bò mà bác rất yêu quý).

Với một xâu \(s\), ta gọi \(B(s)\) là số lượng xâu con liên tiếp "bessie" nhiều nhất có thể đạt được từ xâu \(s\) nếu xoá đi \(0\) hoặc nhiều kí tự trong xâu \(s\). Trong ví dụ trên, \(B(\)"bqessiyexbesszieb"\() = 2\). Và với mỗi xâu \(t\), gọi \(A(t)\) là tổng các \(B(s)\) với \(s\) là xâu con liên tiếp của xâu \(t\).

Bác John đưa cho bạn một xâu \(t\) có độ dài không quá \(2 \times 10^5\) chỉ bao gồm các chữ cái in thường. Hãy tính toán \(A(t)\) và sự thay đổi của \(A(t)\) sau \(U\) \((1 \le 2 \times 10^5)\) lần cập nhật, mỗi lần sẽ thay đổi một kí tự trong xâu \(t\). Mỗi lần cập nhật đều áp dụng trực tiếp lên xâu \(t\).

Input

• Dòng đầu tiên chứa xâu \(t\).
• Dòng tiếp theo chứa số \(U\).
• Trong \(U\) dòng tiếp theo, mỗi dòng gồm số nguyên \(p\) \((1 \le p \le |t|)\) và một chữ cái in thường \(c\), nghĩa là thay đổi \(t_p\) thành \(c\).

Output

• Gồm \(U + 1\) dòng, dòng đầu tiên là \(A(t)\) của xâu \(t\) ban đầu, \(U\) dòng tiếp theo là \(A(t)\) sau mỗi lần cập nhật xâu.

Scoring

• Subtask \(1\): \(|t|, U \le 300\).
• Subtask \(2\): \(U \le 10\).
• Subtask \(3\): \(|t|, U \le 10^5\).
• Subtask \(4\): Không có ràng buộc gì thêm.

bessiebessie
3
3 l
7 s
3 s

14
7
1
7

Với \(2\) số nguyên dương \(a\) và \(b\) bất kì. Ta định nghĩa hàm gen_string(a, b) bởi đoạn code Python sau:

def gen_string(a: int, b: int):
    res = ""
    ia, ib = 0, 0
    while ia + ib < a + b:
        if ia * b <= ib * a:
            res += '0'
            ia += 1
        else:
            res += '1'
            ib += 1
    return res

Tương đương với đoạn code C++ sau:

string gen_string(int64_t a, int64_t b) {
    string res;
    int ia = 0, ib = 0;
    while (ia + ib < a + b) {
        if ((__int128)ia * b <= (__int128)ib * a) {
            res += '0';
            ia++;
        } else {
            res += '1';
            ib++;
        }
    }
    return res;
}

Một xâu nhị phân \(s\) được gọi là "tốt" nếu như tồn tại \(2\) số nguyên dương \(x\) và \(y\) sao cho \(s =\) gen_string(x, y). Bạn được cho \(2\) số \(A\) và \(B\) \((1 \le A, B \le 10^{18})\), bạn cần tính toán số xâu tiền tố "tốt" của xâu gen_string(A, B). Ví dụ, có \(6\) xâu tiền tố "tốt" của xâu gen_string(4, 10):

Input

• Dòng đầu tiên chứa số \(T\) \((T \le 10)\), chỉ số lượng test.
• \(T\) dòng tiếp theo, mỗi dòng chứa \(2\) số \(A\) và \(B\).

Output

• Gồm \(T\) dòng, mỗi dòng là đáp cho mỗi test.

Scoring

• Subtask \(1\): \(A, B \le 100\).
• Subtask \(2\): \(A, B \le 1000\).
• Subtask \(3\): \(A, B \le 10^6\).
• Subtask \(4\): Không có quá \(10^5\) xâu tiền tố tốt trong mỗi test.
• Subtask \(5\): Không có thêm ràng buộc.

6
1 1
3 5
4 7
8 20
4 10
27 21

1
5
7
10
6
13

Có \(N - 1\) cặp bạn bè trong \(N\) chú bò của nông dân John \((2 \le N \le 2 \times 10^5)\) được đánh số từ \(1\) đến \(N\), tạo thành một đồ thị cây. Những chú bò đang rời trang trại lần lượt để đi chơi trong kì nghỉ. Ngày thứ \(i\), chú bò \(i\) sẽ rời trang trại, sau đó tất cả bạn bè của chú ta mà hiện tại vẫn trong trang trại sẽ trở thành bạn của nhau.

Với mỗi \(i \in [1, N]\), ngay trước khi chú bò \(i\) rời khỏi trang trại, bao nhiêu bộ ba có thứ tự \((a, b, c)\) thoả mãn không có chú bò nào trong ba chú bò \(a, b, c\) đang trong kì nghỉ và \(a\) là bạn của \(b\), \(b\) là bạn của \(c\).

Input

• Dòng đầu tiên là số \(N\).
• \(N - 1\) dòng tiếp theo, mỗi dòng gồm \(2\) số \(u_i\) và \(v_i\) cho biết ban đầu \(u_i\) và \(v_i\) là bạn \((1 \le u_i, v_i \le N)\).

Output

• Đáp án với mỗi \(i \in [1, N]\).

Scoring

• Subtask \(1\): \(N \le 500\).
• Subtask \(2\): \(N \le 5000\).
• Subtask \(3\): Không có thêm ràng buộc

3
1 2
2 3

2
0
0

4
1 2
1 3
1 4

6
6
0
0

5
3 5
5 1
1 4
1 2

8
10
2
0
0