Let's consider two cases:

• If $$$ x \geq y $$$. In this case, the blender will mix $$$ \min(y, c) $$$ fruits every second (where $$$ c $$$ is the number of unmixed fruits). Therefore, the answer will be $$$ \lceil \frac{n}{y} \rceil $$$.
• If $$$ x < y $$$. Here, the blender will mix $$$ \min(x, c) $$$ fruits every second. In this case, the answer will be $$$ \lceil \frac{n}{x} \rceil $$$, similarly.

Thus, the final answer is $$$ \lceil \frac{n}{\min(x, y)} \rceil $$$.

#include <iostream>

using namespace std;

int main(){
    int t = 1;
    cin >> t;
    while(t--){
        int n, x, y;
        cin >> n >> x >> y;
        x = min(x, y);
        cout << (n + x - 1) / x << endl;
    }
}

It can be noted that the value of $$$ a_{n-1} $$$ will always be negative in the final result.

Therefore, we can subtract the sum $$$ a_1 + a_2 + \ldots + a_{n-2} $$$ from $$$ a_{n-1} $$$, and then subtract $$$ a_{n-1} $$$ from $$$ a_n $$$.

Thus, the final sum will be $$$ a_1 + a_2 + \ldots + a_{n-2} - a_{n-1} + a_n $$$. This value cannot be exceeded because $$$ a_{n-1} $$$ will always be negative.

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
const int mod = 1e9 + 7;
 
void solve(){
    int n;
    cin >> n;
    ll ans = 0;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin >> a[i];
        ans += a[i];
    }
    cout << ans - 2 * a[n - 2] << '\n';
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}

We will initially maintain an empty string $$$ t $$$ such that $$$ t $$$ appears as a substring in $$$ s $$$.

We will increase the string $$$ t $$$ by one character until its length is less than $$$ n $$$.

We will perform $$$ n $$$ iterations. In each iteration, we will check the strings $$$ t + 0 $$$ and $$$ t + 1 $$$. If one of them appears in $$$ s $$$ as a substring, we will add the appropriate character to the end of $$$ t $$$ and proceed to the next iteration.

If neither of these two strings appears in $$$ s $$$, it means that the string $$$ t $$$ is a suffix of the string $$$ s $$$. After this iteration, we will check the string $$$ 0 + t $$$. If it appears in $$$ s $$$, we will add $$$ 0 $$$ to $$$ t $$$; otherwise, we will add $$$ 1 $$$.

Thus, in each iteration, we perform 2 queries, except for one iteration in which we perform 3 queries. However, after this iteration, we will make only 1 query, so the total number of queries will not exceed $$$ 2 \cdot n $$$.

#include <iostream>
#include <vector>
#include <string>
#include <array>
 
using namespace std;
 
bool ask(string t) {
    cout << "? " << t << endl;
    int res;
    cin >> res;
    return res;
}
 
void result(string s) {
    cout << "! " << s << endl;
}
 
void solve() {
    int n;
    cin >> n;
    string cur;
    while (cur.size() < n) {
        if (ask(cur + "0")) {
            cur += "0";
        } else if (ask(cur + "1")) {
            cur += "1";
        } else {
            break;
        }
    }
    while ((int) cur.size() < n) {
        if (ask("0" + cur)) {
            cur = "0" + cur;
        } else{
            cur = "1" + cur;
        }
    }
    result(cur);
}
 
int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
}

First statement: if $$$ a_i > a_{i+1} $$$, then it is always beneficial to perform an operation at position $$$ i $$$. Therefore, the final array will be non-decreasing.

Second statement: if the array is non-decreasing, then performing operations is not advantageous.

We will maintain a stack that holds a sorted array. Each element in the stack will represent a pair $$$ (x, cnt) $$$, where $$$ x $$$ is the value and $$$ cnt $$$ is the number of its occurrences.

When adding $$$ a_i $$$ to the stack, we will keep track of the sum of the removed elements $$$ sum $$$ from the stack and their count $$$ cnt $$$. Initially, $$$ sum = a_i $$$ and $$$ cnt = 1 $$$. We will remove the last element from the stack while it is greater than $$$ \frac{sum}{cnt} $$$. After that, we recalculate $$$ sum $$$ and $$$ cnt $$$. Then we add the pairs $$$ \left( \frac{sum}{cnt}, cnt - sum \mod cnt \right) $$$ and $$$\left( \frac{sum}{cnt} + 1, sum \mod cnt \right) $$$ to the stack.

The time complexity of the algorithm is $$$ O(n) $$$, since on each iteration, no more than 2 elements are added to the stack, and each element is removed at most once.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll a[200200];
int n;

void solve(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    stack<pair<ll, int>> s;
    for(int i=1;i<=n;i++){
        ll sum = a[i], cnt = 1;
        while(s.size() && s.top().first >= sum / cnt){
            sum += s.top().first * s.top().second;
            cnt += s.top().second;
            s.pop();
        }
        s.push({sum / cnt, cnt - sum % cnt});
        if(sum % cnt != 0){
            s.push({sum / cnt + 1, sum % cnt});
        }
    }
    ll mx = s.top().first;
    while(s.size() > 1){
        s.pop();
    }
    cout << mx - s.top().first << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
}

Let $$$ g $$$ be the greatest common divisor $$$gcd$$$ of the array $$$ a $$$. We will divide each element $$$ a_i $$$ by $$$ g $$$, and at the end, simply multiply the result by $$$ g $$$.

Now, consider the following greedy algorithm. We will start with an initially empty array $$$ b $$$ and add to the end of array $$$ b $$$ the element that minimizes the GCD with the already existing array $$$ b $$$. It can be observed that the $$$gcd$$$ will reach 1 in at most 10 iterations. After that, the remaining elements can be added in any order.

Total time complexty: $$$O(n \cdot 10)$$$.

#include <bits/stdc++.h>

using namespace std;

int a[200200];
int n;

void solve(){
    cin >> n;
    int g = 0, cur = 0;
    long long ans = 0;
    for(int i=0;i<n;i++){
        cin >> a[i];
        g = __gcd(g, a[i]);
    }
    for(int i=0;i<n;i++){
        a[i] /= g;
    }
    for(int t=0;t<n;t++){
        int nc = 1e9;
        for(int i=0;i<n;i++){
            nc = min(nc, __gcd(cur, a[i]));
        }
        cur = nc;
        ans += cur;
        if(cur == 1) {
            ans += n - t - 1;
            break;
        }
    }
    cout << ans * g << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
     cin >> t;
    while(t--){
        solve();
    }
}

First, let's understand how the game proceeds. Alice and Bob start moving toward each other along the path from vertex $$$ 1 $$$ to vertex $$$ u $$$. At some vertex, one of the players can turn into a subtree of a vertex that is not on the path $$$ (1, u) $$$. After this, both players go to the furthest accessible vertex.

Let the path from vertex $$$ 1 $$$ to vertex $$$ u $$$ be denoted as $$$ (p_1, p_2, \dots, p_m) $$$, where $$$ p_1 = 1 $$$ and $$$ p_m = u $$$. Initially, Alice is at vertex $$$ p_1 $$$ and Bob is at vertex $$$ p_m $$$.

For each vertex on the path $$$ (p_1, p_2, \dots, p_m) $$$, we define two values:

• $$$ a_i $$$ — the number of vertices that Alice will visit if she descends into the subtree of vertex $$$ p_i $$$ that does not lie on the path $$$ (1, u) $$$;

• $$$ b_i $$$ — the number of vertices that Bob will visit if he descends into the subtree of vertex $$$ p_i $$$ that also does not lie on this path.

Let the distance to the furthest vertex in the subtree of vertex $$$ p_i $$$ be denoted as $$$ d_{p_i} $$$. Then:

• $$$ a_i = d_{p_i} + i $$$ — the number of vertices Alice can visit if she descends into the subtree at vertex $$$ p_i $$$.

• $$$ b_i = d_{p_i} + m — i + 1 $$$ — the number of vertices Bob can visit if he descends into the subtree at vertex $$$ p_i $$$.

Now, consider what happens if Alice is at vertex $$$ p_i $$$ and Bob is at vertex $$$ p_j $$$. If Alice decides to descend into the subtree of vertex $$$ p_i $$$, she will visit $$$ a_i $$$ vertices. Meanwhile, Bob can reach any vertex on the segment $$$ (p_i, p_{i+1}, \dots, p_j) $$$. It is advantageous for Bob to descend into the subtree of the vertex with the maximum value of $$$ b_k $$$, where $$$ k \in [i+1, j] $$$.

Therefore, it is beneficial for Alice to descend into the subtree of vertex $$$ p_i $$$ if the following condition holds: $$$ a_i > \max(b_{i+1}, b_{i+2}, \dots, b_j) $$$ Otherwise, she should move to vertex $$$ p_{i+1} $$$.

The situation for Bob is similar: he will descend into the subtree of vertex $$$ p_j $$$ if the condition analogous to Alice's condition holds for him.

To efficiently find the maximum on the segment $$$ (p_{i+1}, \dots, p_j) $$$, one can use a segment tree or a sparse table. This allows finding the maximum in $$$ O(\log n) $$$ for each query, resulting in an overall time complexity of $$$ O(n \log n) $$$.

However, it can be proven that instead of using a segment tree or sparse table, one can simply iterate through all vertices on the segment and terminate the loop upon finding a greater vertex. This approach will yield a solution with a time complexity of $$$ O(n) $$$.

#include <bits/stdc++.h>

using namespace std;
const int maxn = 2e5 + 12;

vector<int> g[maxn];
vector<int> ord;
int dp[maxn];
int n, m, k;

bool calc(int v, int p, int f){
    bool is = 0;
    if(v == f) is = 1;
    dp[v] = 1;
    for(int to:g[v]){
        if(to == p){
            continue;
        }
        bool fg = calc(to, v, f);
        is |= fg;
        if(fg == 0){
            dp[v] = max(dp[v], dp[to] + 1);
        }
    }
    if(is){
        ord.push_back(v);
    }
    return is;
}

struct segtree {
    int t[maxn * 4];
    void build (int v, int tl, int tr, vector <int>& a) {
        if (tl == tr) {
            t[v] = a[tl];
            return;
        }
        int tm = (tl + tr) >> 1;
        build (v * 2, tl, tm, a);
        build (v * 2 + 1, tm + 1, tr, a);
        t[v] = max(t[v * 2], t[v * 2 + 1]);
    }
    int get (int v, int tl, int tr, int l, int r) {
        if (tr < l || r < tl) return 0;
        if (l <= tl && tr <= r) return t[v];
        int tm = (tl + tr) >> 1;
        return max(get(v * 2, tl, tm, l, r), get(v * 2 + 1, tm + 1, tr, l, r));
    }
} st_a, st_b;

int get(int v){
    ord.clear();
    calc(1, 0 , v);
    int m = ord.size();
    reverse(ord.begin(), ord.end());
    vector<int> a(m), b(m);
    for(int i=0;i<m;i++){
        a[i] = dp[ord[i]] + i;
        b[i] = dp[ord[m - i - 1]] + i;
    }
    st_a.build(1, 0, m-1, a);
    st_b.build(1, 0, m-1, b);
    for(int i=0;i < (m + 1) / 2;i++){
        if(a[i] > st_b.get(1, 0, m-1, i, m - i - 2)){
            return 1;
        }
        if(b[i] >= st_a.get(1, 0, m-1, i + 1, m - i - 2)){
            return 0;
        }
    }
}

void solve(){
    cin >> n;
    for(int i=1;i<=n;i++){
        g[i].clear();
    }
    for(int i=1;i<n;i++){
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int u, v;
    cin >> u >> v;
    ord.clear();
    calc(v, 0, u);
    auto p = ord;
    for(int x:p){
        if(get(x) == 1){
            cout << "Alice\n";
        }
        else{
            cout << "Bob\n";
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
}

#include <bits/stdc++.h>

using namespace std;

int dfs(int v, int p, int to, const vector<vector<int>> &g, vector<int> &max_depth) {
    int ans = 0;
    bool has_to = false;
    for (int i : g[v]) {
        if (i == p) {
            continue;
        }
        int tmp = dfs(i, v, to, g, max_depth);
        if (tmp == -1) {
            has_to = true;
        } else {
            ans = max(ans, tmp + 1);
        }
    }
    if (has_to || v == to) {
        max_depth.emplace_back(ans);
        return -1;
    } else {
        return ans;
    }
}

int solve(const vector<vector<int>> &g, int to) {
    vector<int> max_depth;
    dfs(0, -1, to, g, max_depth);
    int n = max_depth.size();
    reverse(max_depth.begin(), max_depth.end());
    int first = 0, second = n - 1;
    while (true) {
        {
            int value1 = max_depth[first] + first;
            bool valid = true;
            for (int j = second; j > first; --j) {
                if (value1 <= max_depth[j] + (n - j - 1)) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                return 0;
            }
            ++first;
            if (first == second) {
                return 1;
            }
        }
        {
            int value2 = max_depth[second] + (n - second - 1);
            bool valid = true;
            for (int j = first; j < second; ++j) {
                if (value2 < max_depth[j] + j) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                return 1;
            }
            --second;
            if (first == second) {
                return 0;
            }
        }
    }
}

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        g[a - 1].push_back(b - 1);
        g[b - 1].push_back(a - 1);
    }
    int s, f;
    cin >> s >> f;
    --s, --f;
    int ans = solve(g, s);
    if (ans == 0) {
        cout << "Alice\n";
    } else {
        cout << "Bob\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--)
        solve();
}

Read the Solution of the easy version of the problem.

The path $$$ (u, v) $$$ can be divided into two vertical paths $$$ (1, u) $$$ and $$$ (1, v) $$$. We will solve for the vertices on the path $$$ (1, u) $$$, while the path $$$ (1, v) $$$ is solved similarly.

For each vertex on the path $$$ (1, u) $$$, we define two values:

• $$$ fa_i $$$ — the first vertex at which Alice will win if she descends into the subtree when Bob starts at vertex $$$ p_i $$$.
• $$$ fb_i $$$ — the first vertex at which Bob will win if he descends into the subtree when he starts at vertex $$$ p_i $$$.

The claim is that it is beneficial for Alice to descend into the subtree at vertex $$$ v $$$ only over a certain segment of vertices from which Bob starts. A similar claim holds for Bob.

Now, for each of Alice's vertices, we need to determine the segment where it is beneficial to descend. The left boundary of the segment for vertex $$$ p_i $$$ will be $$$ 2 \cdot i $$$, since Alice will always be on the left half of the path. It is easy to notice that the right boundary of the segment can be found using binary search.

We redefine the value $$$ b_i $$$ to be $$$ d_{p_i} - i $$$. To check whether it is beneficial for us to descend into the subtree for a fixed midpoint $$$ mid $$$, we need to satisfy the following condition: $$$ a_i > \max(b_{i+1}, b_{i+2}, \ldots, b_{mid - i}) + mid. $$$

Let $$$ (l_j, r_j) $$$ denote the segment where it is beneficial for Alice to descend if Bob starts at vertex $$$ p_j $$$. Then the value $$$ fa_i $$$ will be the minimum position $$$ j $$$ such that $$$ l_j \leq i \leq r_j $$$; this can be found using a set.

The value $$$ fb_i $$$ is calculated similarly.

Alice wins at vertex $$$ p_i $$$ if $$$ fa_i \leq i - fb_i $$$; otherwise, Bob wins.

To efficiently find the maximum on the segment, a sparse table can be used. Additionally, using sets and binary searches gives us a time complexity of $$$ O(n \log n) $$$.

#include <bits/stdc++.h>

using namespace std;
const int maxn = 2e5 + 12;

vector<int> g[maxn], del[maxn], add[maxn];
vector<int> ord;
int ans[maxn];
int dp[maxn];
int n, m, k;

bool calc(int v, int p, int f){
    bool is = 0;
    if(v == f) is = 1;
    dp[v] = 1;
    for(int to:g[v]){
        if(to == p){
            continue;
        }
        bool fg = calc(to, v, f);
        is |= fg;
        if(fg == 0){
            dp[v] = max(dp[v], dp[to] + 1);
        }
    }
    if(is){
        ord.push_back(v);
    }
    return is;
}

struct sparse {
    int mx[20][200200], lg[200200];
    int n;
    void build(vector<int> &a){
        n = a.size();
        for(int i=0;i<n;i++){
            mx[0][i] = a[i];
        }
        lg[0] = lg[1] = 0;
        for(int i=2;i<=n;i++){
            lg[i] = lg[i/2] + 1;
        }
        for(int k=1;k<20;k++){
            for(int i=0;i + (1 << k) - 1 < n;i++){
                mx[k][i] = max(mx[k-1][i], mx[k-1][i + (1 << (k - 1))]);
            }
        }
    }
    int get (int l, int r) {
        if(l > r) return -1e9;
        int k = lg[r-l+1];
        return max(mx[k][l], mx[k][r - (1 << k) + 1]);
    }
} st_a, st_b;

void solve(int v){
    ord.clear();
    calc(1, 0, v);
    reverse(ord.begin(), ord.end());
    m = ord.size();
    vector<int> a(m+1), b(m+1);
    vector<int> fa(m+1, 1e9), fb(m+1, -1e9);
    for(int i=0;i<m;i++){
        a[i] = dp[ord[i]] + i;
        b[i] = dp[ord[i]] - i;
        del[i].clear();
        add[i].clear();
    }
    st_a.build(a);
    st_b.build(b);
    multiset<int> s;
    for(int i=1;i<m;i++){
        int pos = i;
        for(int l=i+1, r=m-1;l<=r;){
            int mid = l + r >> 1;
            if(st_b.get(i+1 , mid) + mid < a[i] - i){
                pos = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        if(i < pos){
            add[min(m, 2 * i)].push_back(i);
            del[min(m, pos + i)].push_back(i);
        }
        for(int x:add[i]){
            s.insert(x);
        }
        if(s.size()) fa[i] = *s.begin();
        for(int x:del[i]){
            s.erase(s.find(x));
        }
    }
    s.clear();
    for(int i=0;i<=m;i++){
        add[i].clear();
        del[i].clear();
    }
    for(int i=1;i<m;i++){
        int pos = i;
        for(int l=1, r = i-1;l<=r;){
            int mid = l + r >> 1;
            if(st_a.get(mid, i-1) - mid + 1 <= b[i] + i){
                pos = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        pos--;
        if(pos >= 0){
            add[min(m, pos + i)].push_back(i);
            del[min(m, 2 * i - 1)].push_back(i);
        }
        for(int x:add[i]){
            s.insert(x);
        }
        if(s.size()) fb[i] = *s.rbegin();
        for(int x:del[i]){
            s.erase(s.find(x));
        }
    }
    for(int i=m-1;i>0;i--){
        b[i] = max(b[i+1] + 1, dp[ord[i]]);
        if(b[i] >= st_a.get(1, i-1)){
            fb[i] = i;
        }
        if(a[0] > max(st_b.get(1, i-1) + i, b[i])){
            fa[i] = 0;
        }
        ans[ord[i]] = 0;
        if(fa[i] <= i - fb[i]){
            ans[ord[i]] = 1;
        }
    }
}

void solve(){
    cin >> n;
    for(int i=1;i<=n;i++){
        g[i].clear();
    }
    for(int i=1;i<n;i++){
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int u, v;
    cin >> u >> v;
    solve(u), solve(v);
    ord.clear();
    calc(v, 0, u);
    auto p = ord;
    for(int x:p){
        if(ans[x] == 1){
            cout << "Alice\n";
        }
        else{
            cout << "Bob\n";
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
}