B turned out to be harder than expected. I apologize for this, but I hope there are still problems that are fun and educational for you to solve in this round.

Regardless, I hope this round encourages authors to include communication problems in their future rounds, and in earlier positions as well.

Suppose it Kalamaki's turn on some even round $$$2k$$$. Kalamaki can swap element $$$a_{2k}$$$ with $$$a_{2k+1}$$$. If $$$a_{2k} \gt a_{2k+1}$$$, he will not swap the elements, but if $$$a_{2k} \lt a_{2k+1}$$$, he will swap them. In both cases he wins the game, because the array will never be sorted. Therefore, if $$$a_{2k} \neq a_{2k+1}$$$, Kalamaki will win no matter what.

Now assume every time Kalamaki plays, the two elements he can swap have the same value, because otherwise we have shown that he wins. Suppose that it is Souvlaki's turn on round $$$2k+1$$$. We know that $$$a_{2k} = a_{2k+1}$$$ from the previous assumption. If $$$a_{2k+1} \gt a_{2k+2}$$$, we know that $$$a_{2k+1} = a_{2k} \gt a_{2k+2}$$$, but he is unable to swap $$$a_{2k}$$$ and $$$a_{2k+2}$$$, therefore he loses. Otherwise, if $$$a_{2k+1} \le a_{2k+2}$$$ he will not do anything, and he proceeds to the next round.

From these observations, we see that $$$a$$$ is winnable by Souvlaki if and only if: $$$a_1 \le a_2 = a_3 \le a_4 = a_5 \le \ldots$$$, or $$$a_2 \le a_1 = a_3 \le a_4 = a_5 \le \ldots$$$. It is obvious now that Souvlaki, before the start of the game, will sort $$$a$$$ in non-decreasing order. To determine if Souvlaki wins or not it is enough to check the above condition is satisfied after sorting.

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
    int n; cin >> n;
    int a[n+1];
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a+1, a+n+1);
    for (int i = 2; i <= n - 1; i+=2) {
        if (a[i] != a[i+1]) {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}
 
int main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Amazing
• Good
• Average
• Bad

• Very Hard
• Hard
• Average
• Easy
• Very Easy

Let the position of integer $$$x$$$ in the permutation $$$p$$$ be denoted by $$$pos_x$$$.

Let's see for which indices $$$i$$$ we can never set $$$s_i$$$ to $$$1$$$, even with an infinite number of operations. First of all, in an operation $$$(l, r)$$$, we only consider indices $$$i$$$ such that $$$l \lt i \lt r$$$. This means that we can never set $$$s_1$$$ or $$$s_n$$$ to $$$1$$$. In addition, we only consider indices $$$i$$$ such that $$$p_i$$$ is between $$$p_l$$$ and $$$p_r$$$, but not equal to those. This means that we can never set $$$s_{pos_1}$$$ or $$$s_{pos_n}$$$ to $$$1$$$. In general, if $$$x_1 = 1$$$, $$$x_n = 1$$$, $$$x_{pos_1} = 1$$$, or $$$x_{pos_n} = 1$$$, it is impossible to solve the problem.

Now I will show that the problem is always solvable for any binary string $$$x$$$ such that $$$x_1 = x_n = x_{pos_1} = x_{pos_n} = 0$$$, within $$$5$$$ operations.

WLOG, assume $$$pos_1 \lt pos_n$$$. It is natural to think about using $$$pos_1$$$ and $$$pos_n$$$ as endpoints for our operations. For example, by using the operations $$$(1, pos_1)$$$ and $$$(1, pos_n)$$$, we will have set $$$s_i = 1$$$ for every $$$1 \lt i \lt pos_1$$$. Likewise, with the operations $$$(pos_1, n)$$$ and $$$(pos_n, n)$$$, we will have set $$$s_i = 1$$$ for every $$$pos_n \lt i \lt n$$$. By using the operation $$$(pos_1, pos_n)$$$, we have set $$$s_i = 1$$$ for every $$$pos_1 \lt i \lt pos_n$$$.

With these $$$5$$$ operations, we have finally set $$$s_i = 1$$$ for every $$$i$$$ in $$$(1, pos_1) \cup (pos_1, pos_n) \cup (pos_n, n)$$$, which guarantees we have solved the problem.

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
    int n; cin >> n;
    vector<int> a(n+1);
    int mn = 1, mx = 1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] < a[mn]) mn = i;
        if (a[i] > a[mx]) mx = i;
    }
    string t; cin >> t;
    t = " " + t;
    if (t[1] == '1' || t[n] == '1') {
        cout << -1 << "\n";
        return;
    }
    if (t[mn] == '1' || t[mx] == '1') {
        cout << -1 << "\n";
        return;
    }
    cout << 5 << "\n";
    cout << 1 << " " << mn << "\n";
    cout << 1 << " " << mx << "\n";
    cout << mn << " " << n << "\n";
    cout << mx << " " << n << "\n";
    cout << min(mn, mx) << " " << max(mn, mx) << "\n";
}
 
int main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Amazing
• Good
• Average
• Bad

• Very Hard
• Hard
• Average
• Easy
• Very Easy

We call a pair of integers $$$(l, r)$$$ good if and only if $$$1 \le l \le r \le 2n$$$ and in $$$f(l, r)$$$ there is a down-right path from $$$(1, 1)$$$ to $$$(2, n)$$$ of cells with value of $$$1$$$. For some fixed left endpoint $$$l$$$ from $$$1$$$ to $$$2n$$$, let $$$r_l$$$ denote the minimum integer such that the pair $$$(l, r_l)$$$ is good. If there does not exist such an integer, for convenience we say $$$r_l = n+1$$$.

The first observation is that if $$$(l, r)$$$ is good, and $$$r \lt 2n$$$, then $$$(l, r+1)$$$ is also good. The reason is obvious: every cell that has value of $$$1$$$ in $$$f(l, r)$$$ has value of $$$1$$$ in $$$f(l, r+1)$$$. Therefore, if we find $$$r_1, r_2, \ldots, r_{2n}$$$, the answer will be $$$(2n - r_1 + 1) + (2n - r_2 + 1) + \ldots + (2n - r_{2n} + 1)$$$. (In other words, we are counting all pairs $$$(l, r_l), (l, r_l+1), \ldots, (l, 2n)$$$, for all $$$1 \le l \le 2n$$$).

The second observation follows: $$$r_1 \le r_2 \le \ldots \le r_{2n}$$$. It is clear that the only difference between grids $$$f(l, r_l)$$$ and $$$f(l+1, r_l)$$$ is that $$$f(l+1, r_l)$$$ has the same or a greater amount of cells with value of $$$0$$$, and if some cell has value of $$$1$$$ in $$$f(l+1, r_l)$$$, it has value of $$$1$$$ in $$$f(l, r_l)$$$. If we do not have a down-right path anymore in $$$f(l+1, r_l)$$$, there is no down right path in any $$$f(l+1, r)$$$ with $$$r \le r_l$$$. It follows that $$$r_{l+1} \ge r_l$$$.

This observation allows us to use two pointers. For some fixed $$$l$$$ and $$$r$$$, if $$$(l, r)$$$ is not good, we will keep increasing $$$r$$$ until it is good, or in other words find $$$r_l$$$. We activate all cells with value of $$$r+1$$$. To check if the pair $$$(l, r+1)$$$ is good, we get the first de-activated cell in the first row and the last de-activated cell in the last row (a cell is de-activated if it does not belong in the range we are currently considering). This can be done by keeping two sets of de-activated cells, one for each row. Suppose that those are at columns $$$a$$$ and $$$b$$$ respectively. There exists a down-right path in $$$f(l, r+1)$$$ if and only if $$$a - 1 \gt b$$$ (we can reach cell $$$(1, a-1)$$$, then go to cell $$$(2, a-1)$$$ and the proceed to $$$(2, n)$$$). Once we find $$$r_l$$$, we will increase $$$l$$$, de-activate every cell with value of $$$l$$$, and keep increasing $$$r_l$$$ until we find $$$r_{l+1}$$$, and so on.

// nifeshe

#ifdef LOCAL
    #include <bits/include_all.h>
#else
    #include <bits/stdc++.h>
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
#endif

#pragma GCC target ("avx2")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define int long long

using namespace std;
using namespace __gnu_pbds;

template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const ll mod = 998244353;
const ll inf = 1e18;
const int MAX = 2e5 + 42;

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<ll> dis(1, inf);

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> a(2, vector<int>(n));
    for(auto &i : a) {
        for(auto &j : i) {
            cin >> j;
        }
    }

    vector<vector<pii>> pos(2 * n + 1);
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < n; j++) {
            pos[a[i][j]].push_back({i, j});
        }
    }


    array<set<int>, 2> st;
    st[0].insert(inf);
    st[1].insert(-inf);
    for(int i = 0; i < n; i++) st[0].insert(i);
    for(int i = 0; i < n; i++) st[1].insert(i);

    auto add = [&](int x) {
        for(auto [i, j] : pos[x]) {
            st[i].erase(j);
        }
    };

    auto del = [&](int x) {
        for(auto [i, j] : pos[x]) {
            st[i].insert(j);
        }
    };

    auto check = [&]() {
        if(st[0].count(0)) return false;
        if(st[1].count(n - 1)) return false;
        if(*st[0].begin() - 1 <= *st[1].rbegin()) return false;

        return true;
    };

    int ans = 0;
    int r = 0;
    for(int l = 1; l <= 2 * n; l++) {
        while(r + 1 <= 2 * n && !check()) {
            add(++r);
        }
        if(!check()) break;

        ans += 2 * n - r + 1;
        del(l);
    }

    cout << ans << '\n';
}

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

• Amazing
• Good
• Average
• Bad

• Very Hard
• Hard
• Average
• Easy
• Very Easy

First, observe that if a range is completely inside another, it is useless. Specifically, assume we have two ranges $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$. If $$$1 \le l_2 \le l_1 \le r_1 \le r_2 \le n$$$, then we know that $$$\operatorname{MEX}(p[l_1 \ldots r_1]) \le \operatorname{MEX}(p[l_2 \ldots r_2])$$$. So we must only consider the range $$$[l_2, r_2]$$$.

After cleaning out those ranges, we are left with at most $$$n$$$ ranges. This is obvious because for every possible left endpoint, we have at most one possible right endpoint (the maximum one among all given ranges).

Now, suppose we also knew the position of $$$0$$$. Let it be $$$p_0$$$. We know that if some range does not include $$$p_0$$$, it is also useless. I claim that removing these ranges leaves at most $$$\lceil \frac{n}{2} \rceil$$$ possible ranges we must consider. Specifically, if $$$p_0 \le \frac{n}{2}$$$, we only consider ranges with left endpoint before than $$$p_0$$$. Otherwise, if $$$p_0 \ge \frac{n}{2}$$$, we only consider ranges with right endpoint after $$$p_0$$$. In both cases, it is obvious we consider at most $$$\lceil \frac{n}{2} \rceil$$$ ranges.

Finally, notice that we do not care about the exact value of $$$p_0$$$, but only if it is in the first half or the second half. Therefore, we will do a query of the form $$$[1, \frac{n}{2}]$$$, determine which half $$$p_0$$$ is in, clean out useless ranges and query the rest. This results to at most $$$\lceil \frac{n}{2} \rceil + 1$$$ queries, and the problem is solved.

#include <bits/stdc++.h>
using namespace std;
 
int LIM, Q;
 
int ask(int l, int r) {
    Q++;
    assert(Q <= LIM);
    cout << "? " << l << " " << r << endl;
    int ans; cin >> ans;
    return ans;
}
 
bool inside(int l, int r, bool toL, int n) {
    int midL = n / 2;
    if (toL) {
        return l <= midL;
    }
    else return r > midL;
}
 
void solve() {
    int n, q; cin >> n >> q;
    Q = 0;
    LIM = max(30, n / 2 + n % 2 + 5);
    vector<int> maxR(n+1, 0);
    for (int i = 1; i <= q; i++) {
        int l, r; cin >> l >> r;
        maxR[l] = max(maxR[l], r);
    }
    bool toL = (ask(1, n/2) > 0);
    int ans = 0, mx = 0;
    for (int i = 1; i <= n; i++) {
        if (maxR[i] > mx && inside(i, maxR[i], toL, n)) {
            ans = max(ans, ask(i, maxR[i]));
        }
        mx = max(mx, maxR[i]);
    }
    cout << "! " << ans << endl;
}
 
int main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Amazing
• Good
• Average
• Bad

• Very Hard
• Hard
• Average
• Easy
• Very Easy

Please read the first two paragraphs of the solution to the Easy Version first. Suppose we have cleaned out the ranges that are completely inside other ranges.

A useful property to consider, is that for a range $$$[l, r]$$$ it holds that $$$\operatorname{MEX}(p[l...r]) = \min(\operatorname{MEX}(p[1...r]), \operatorname{MEX}(p[l...n]))$$$. To prove this, consider the first non-negative integer $$$k$$$ such that it does not appear in $$$p[l...r]$$$. In other words, $$$\operatorname{MEX}(p[l...r]) = k$$$. If $$$k$$$ appears to the left of the range, we have $$$\operatorname{MEX}(p[1...r]) \gt k$$$ and $$$\operatorname{MEX}(p[l...n]) = k$$$. Otherwise, we have $$$\operatorname{MEX}(p[1...r]) = k$$$ and $$$\operatorname{MEX}(p[l...n]) \gt k$$$. In both cases, it holds $$$k = \operatorname{MEX}(p[l...r]) = \min(\operatorname{MEX}(p[1...r]), \operatorname{MEX}(p[l...n]))$$$.

Consider a set of ranges $$$S$$$, such that no range is completely inside another. Picking a range $$$[l, r]$$$ of this set splits $$$S$$$ to two subsets: one set $$$L$$$ includes all ranges $$$[l_1, r_1]$$$ such that $$$l_1 \lt l$$$, and the other set $$$R$$$ includes all ranges $$$[l_2, r_2]$$$ such that $$$l \lt l_2$$$. If we could find the best subset to keep searching in depending on $$$[l, r]$$$, we could perform binary search and find the answer quickly.

So we now have the subproblem: given a range $$$[l, r]$$$, figure out if the oprimal subset to search is $$$L$$$ or $$$R$$$. We will use the following properties:

• $$$\operatorname{MEX}(p[1...i]) \le \operatorname{MEX}(p[1...i+1])$$$.
• $$$\operatorname{MEX}(p[i+1...n]) \le \operatorname{MEX}(p[i...n])$$$.
• $$$\operatorname{MEX}(p[l...r]) = \min(\operatorname{MEX}(p[1...r]), \operatorname{MEX}(p[l...n]))$$$

Suppose $$$a = \operatorname{MEX}(p[1...r])$$$ and $$$b = \operatorname{MEX}(p[l...n])$$$. If $$$a \lt b$$$, we have no reason to go to $$$L$$$. This is because the prefix $$$\operatorname{MEX}$$$ will keep decreasing, but the suffix $$$\operatorname{MEX}$$$ will keep increasing, so we will always pick the prefix which is definitely not as great as the current $$$a$$$. Therefore, we will move to $$$R$$$. Likewise, if $$$a \gt b$$$, we will move to $$$L$$$. Note that the case $$$a = b$$$ is only possible if $$$[l..r] = [1...n]$$$, in which case the answer is $$$n$$$.

Therefore, for each range we consider we make $$$2$$$ queries, and we do this with binary search at most $$$\log{n}$$$ times. We have solved the problem in $$$2\log{n}$$$ queries.

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
int ask(int l, int r) {
    cout << "? " << l << " " << r << endl;
    int ans; cin >> ans;
    return ans;
}
 
void solve() {
    int n, q; cin >> n >> q;
    vector<int> maxR(n+1, -1);
    for (int i = 1; i <= q; i++) {
        int u, v; cin >> u >> v;
        maxR[u] = max(maxR[u], v);
    }
    vector<pair<int, int>> ranges;
    int mr = 0;
    for (int i = 1; i <= n; i++) {
        if (maxR[i] > mr) {
            mr = maxR[i];
            ranges.push_back({i, maxR[i]});
        }
    }
    q = ranges.size();
    int lo = 0, hi = q-1;
    int ans = 0;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        int l = ranges[mid].first;
        int r = ranges[mid].second;
        int pref = ask(1, r);
        int suff = ask(l, n);
        ans = max(ans, min(pref, suff));
        if (pref > suff) {
            hi = mid-1;
        }
        else lo = mid+1;
    }
    cout << "! " << ans << endl;
}
 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Amazing
• Good
• Average
• Bad

• Very Hard
• Hard
• Average
• Easy
• Very Easy

First, we consider an easier version of the problem: what if every cell of the first column had the same value?

Suppose that every cell of the first column has value of $$$1$$$. We have the following information:

• No matter which row Player A sends, the first cell of that row has value of $$$1$$$.
• Player A has the choice of sending a column full of $1$s.
• If $$$C = 0$$$, there exists a cell with value of $$$0$$$. ($$$C = 0$$$ and every cell having value of $$$1$$$ is a contradiction).

This information leads us to the following strategy. If $$$C = 1$$$, Player A may send any row and the first column. Otherwise, if $$$C = 0$$$, he can send any row and find a column that has a $$$0$$$ in it. Then, Player B can simply compare the first cell of the row with every cell of the column; if they all match, the answer is $$$1$$$, and otherwise it is $$$0$$$.

If every cell of the first column is $$$0$$$, the solution is the same. Note there must exist at least one $$$1$$$ in the grid, as mentioned in the statement (connectivity would not be well defined otherwise). So if $$$C = 0$$$ Player A sends any row and the first column, and otherwise if $$$C = 1$$$ he sends any row and finds a column which includes a $$$1$$$. Again, Player B will compare the value of the first cell of the row with the value every cell of the column, and if they match he answers $$$0$$$ and $$$1$$$ otherwise.

Now we can generalize this solution the case where there exists both a $$$0$$$ and a $$$1$$$ in the first column. Player B always compares the first cell of the row he received: if there exists a cell with different value in the column he determines the answer is the opposite of the value of the first cell of the row. We know the following:

• Player A can send a column with both a $$$0$$$ and a $$$1$$$ (The first column).
• Player A can choose a row, such that its first cell has value $$$0$$$.
• Player A can choose a row, such that its first cell has value $$$1$$$.

Therefore, Player A can always choose the first column and the appropriate row according to $$$C$$$ such that the previous strategy still works for Player B.

#include <bits/stdc++.h>
using namespace std;
 
int ask(vector<vector<bool>> &grid, vector<pair<int, int>> arr, int op) {
    int ans = 0;
    if(op==0) ans=1;
    for (auto [a, b]: arr) {
        if(op) ans=ans||grid[a][b];
        else ans=ans&&grid[a][b];
    }
    return ans;
}
 
void ans(bool x) {
    cout << x << endl;
}
 
int find_row(vector<vector<bool>> &grid, int need, int n) {
    int lo = 1, hi = n;
    int fin = 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        vector<pair<int, int>> qr;
        for (int i = 1; i <= mid; i++) qr.push_back({i, 1});
        if (need == ask(grid, qr, need)) {
            fin = mid;
            hi = mid-1;
        } 
        else lo = mid+1;
    }
    return fin;
}
 
int find_col(vector<vector<bool>> &grid, int need, int n) {
    int lo = 1, hi = n;
    int fin = 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        vector<pair<int, int>> qr;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= mid; j++) {
                qr.push_back({i, j});
            }
        }
        if (need == ask(grid, qr, need)) {
            fin = mid;
            hi = mid-1;
        }
        else lo = mid+1;
    }
    return fin;
}
 
void send_grid() {
    int n; cin >> n;
    bool ans; cin >> ans;
    vector<vector<bool>> grid(n+1, vector<bool>(n+1));
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for(int j = 0; j < n; j++) if(s[j]=='1') grid[i+1][j+1]=1;
    }
    vector<pair<int, int>> qr;
    for (int i = 1; i <= n; i++) {
        qr.push_back({i, 1});
    }
    int o = ask(grid, qr, 1), a = ask(grid, qr, 0);
    int col, row;
    if (o == 1 && a == 0) {
        col = 1;
        row = find_row(grid, !ans, n);
    }
    else if (o == 0) {
        row = 1;
        if (ans == 0) col = 1;
        else col = find_col(grid, 1, n);
    }
    else {
        row = 1;
        if (ans == 1) col = 1;
        else col = find_col(grid, 0, n);
    }
    cout << row << " " << col << endl; 
}
 
void receive_grid() {
    int n; cin >> n;
    string row,col;
    cin >> row >> col;
    bool diff = false;
    for (int i = 0; i < n; i++) {
        if (col[i] != row[0]) diff = true;
    }
    if (diff) {
        ans(!(row[0]=='1'));
    }
    else {
        ans((row[0]=='1'));
    }
}
 
void solve() {
    string run; cin >> run;
    int t; cin >> t;
    if (run == "first") for (int i = 1; i <= t; i++) send_grid();
    else for (int i = 1; i <= t; i++) receive_grid();
}
 
int main() {
    int t = 1;
    while (t--) solve();
    return 0;
}

• Amazing
• Good
• Average
• Bad

• Very Hard
• Hard
• Average
• Easy
• Very Easy

• Amazing
• Good
• Average
• Bad

• Very Hard
• Hard
• Average
• Easy
• Very Easy

• A
• B
• C
• D
• E
• F
• G1
• G2

• A
• B
• C
• D
• E
• F
• G1
• G2

Every character of $$$a$$$ is flipped in exactly one string. Therefore, if $$$a_i = 1$$$, we need to add $$$n-1$$$ to the answer (since the $$$i$$$-$$$th$$$ character will stay $$$1$$$ for $$$n-1$$$ strings), and if $$$a_i = 0$$$ we need to add $$$1$$$ (since the $$$i$$$-$$$th$$$ character will be $$$1$$$ in exactly one string).

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
    int n; cin >> n;
    string s; cin >> s;
    int ans = 0;
    for (auto x: s) {
        if (x == '0') ans++;
        else ans += n - 1;
    }
    cout << ans << '\n';
}
 
int main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Amazing
• Good
• Average
• Bad
• Didn't Solve

If $$$x = n$$$ then we can output any permutation, since in order for the $$$\operatorname{MEX}$$$ to be equal to $$$n$$$, every value $$$0, 1, ..., n-1$$$ must appear. Otherwise, we want to build a permutation $$$p$$$ such that two main conditions hold.

Firstly, we want $$$x$$$ to appear on the final strip as soon as possible. In other words, the first index $$$i$$$ such that $$$\operatorname{MEX}(p_1, p_2, ..., p_i) = x$$$ must be minimized. In addition, the index $$$j$$$ such that $$$p_j = x$$$ must be maximized, since the $$$\operatorname{MEX}$$$ of a set that contains $$$x$$$ cannot be equal to $$$x$$$.

There are a lot of constructions that satisfy those conditions. One of them is the permutation $$$p = [0, 1, ..., x-1, x+1, ..., n-1, x]$$$.

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
    int n, x; cin >> n >> x;
    for (int i = 0; i < x; i++) cout << i << " ";
    for (int i = x+1; i < n; i++) cout << i << " ";
    if (x < n) cout << x;
    cout << '\n';
}
 
int main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Amazing
• Good
• Average
• Bad
• Didn't Solve

Suppose that the two arrays $$$a$$$ and $$$b$$$ of size $$$n$$$ are called $$$s$$$-complementary if and only if $$$a_i + b_i = s$$$ for all $$$1 \le i \le n$$$.

Observation 1: If we know every element of $$$a$$$, and we know $$$s$$$, we can uniquely determine the elements of $$$b$$$.

We split the problem into two cases.

The first case is if there exists at least one element in $$$b$$$ that is not missing. Then we know the required sum $$$s = a_i + b_i$$$ for every $$$1 \le i \le n$$$. For every index $$$i$$$, we know $$$b_i = s - a_i$$$. If $$$0 \le s - a_i \le k$$$ doesn't hold for some index, the answer is $$$0$$$, since it is impossible for the two arrays to be complementary while $$$0 \le b_i \le k$$$. Otherwise, the answer is $$$1$$$ from Observation 1.

The second case is if every element of $$$b$$$ is missing:

Observation 2: if $$$a$$$ and $$$b$$$ are $$$s$$$-complementary, then the maximum element of $$$b$$$ is positioned at the index where the minimum element of $$$a$$$ is positioned at. That is because in order for $$$a_i + b_i = s$$$ to hold when $$$a_i$$$ is minimum, $$$b_i$$$ must be maximized.

Observation 3: The maximum element of $$$b$$$ must be at least $$$mx_a - mn_a$$$, i.e. the difference between the maximum and minimum elements of $$$a$$$.

From Observation 3 and 1, we can set the maximum element of $$$b$$$ to $$$mx_a - mn_a, mx_a - mn_a + 1, ..., k$$$, which results to $$$k - (mx_a - mn_a) + 1$$$ different solutions.

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
    int n, k; cin >> n >> k;
    int a[n], b[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    int s = -1;
    for (int i = 0; i < n; i++) {
        if (b[i] != -1) {
            if (s == -1) s = a[i] + b[i];
            else {
                if (s != a[i] + b[i]) {
                    cout << 0 << '\n';
                    return;
                }
            }
        }
    }
    if (s == -1) {
        sort(a, a+n);
        int mx = a[n-1] - a[0];
        cout << k - mx + 1 << '\n';
        return;
    }
    for (int i = 0; i < n; i++) {
        if (a[i] > s || s - a[i] > k) {
            cout << 0 << '\n';
            return;
        }
    }
    cout << 1 << '\n';
}
 
int main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Amazing
• Good
• Average
• Bad
• Didn't Solve

There is a greedy strategy. Every time you see some flower in $$$a$$$, if its beauty is not less than the beauty of next flower you must pick from $$$b$$$, you will pick it. The answer is $$$0$$$ if we run the greedy without inserting a new flower in $$$a$$$ and still collecting all $$$m$$$ needed flowers.

Now, consider what inserting a new flower of beauty $$$k$$$ in $$$a$$$ will do. It will allow you to "skip" some flower listed in $$$b$$$, as you can place it anywhere in $$$a$$$ and just pick it up when necessary. Therefore, instead of inserting a new element, we can reconsider the problem as deleting some element listed in $$$b$$$. So, one slow solution would be to try deleting $$$b_1$$$, then running the greedy on $$$a$$$, and repeat for $$$b_2$$$, $$$b_3, ..., b_m$$$. Then, we can keep the minimum $$$b_i$$$ such that the greedy was successful when deleting that flower.

The solution is too slow. Instead, we can compute for every index $$$1 \le i \le m$$$ the minimum index $$$j$$$ such that if we run the greedy on the prefix $$$a_1, a_2, ..., a_j$$$, we will have collected flowers $$$b_1, b_2, ..., b_i$$$. Let this value for index $$$i$$$ of $$$b$$$ be $$$p_i$$$. Do the same for each suffix of $$$a$$$. Specifically, let $$$s_i$$$ be the maximum index $$$j$$$ such that if we run the greedy on the suffix $$$a_j, a_{j+1}, ..., a_n$$$ we would have collected the flowers $$$b_i, b_{i+1}, ..., b_m$$$. These values can be calculated with two pointers.

Now, we can delete $$$b_j$$$ if $$$p_{j-1} \lt s_{j+1}$$$ (to delete $$$b_1$$$, it must be that $$$s_{2} \gt 0$$$ and to delete $$$b_m$$$ that $$$p_{m-1} \le n$$$). We keep the minimum among all deletable values in $$$b$$$. If there does not exist such a value the answer is $$$-1$$$.

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 5;
 
int main(){
    int T; cin >> T;
    while(T--){
        int N, M; cin >> N >> M;
        vector<int> a(N), b(M);
        for(int i = 0; i < N; i++) cin >> a[i];
        for(int i = 0; i < M; i++) cin >> b[i];
        vector<int> backwards_match(M);
        int j = N - 1;
        for(int i = M - 1; i >= 0; i--){
            while(j >= 0 && a[j] < b[i]) j--;
            backwards_match[i] = j--;
        }
        vector<int> forwards_match(M);
        j = 0;
        for(int i = 0; i < M; i++){
            while(j < N && a[j] < b[i]) j++;
            forwards_match[i] = j++;
        }
        if(forwards_match.back() < N){
            cout << 0 << endl;
            continue;
        }
        int ans = INF;
        for(int i = 0; i < M; i++){
            int match_previous = i == 0 ? -1 : forwards_match[i - 1];
            int match_next = i + 1 == M ? N : backwards_match[i + 1];
            if(match_next > match_previous){
                ans = min(ans, b[i]);
            }
        }
        cout << (ans == INF ? -1 : ans) << "\n";
    }
}

• Amazing
• Good
• Average
• Bad
• Didn't Solve

Consider some permutation $$$p_1, p_2, ..., p_n$$$. Before answering queries, precompute the index of integer $$$i$$$ $$$(1 \le i \le n)$$$, suppose it is represented as $$$idx_i$$$.

Let's see how to answer some query $$$l, r, x$$$. Obviously, if $$$idx_x$$$ does not belong in the range $$$[l, r]$$$, the answer is $$$-1$$$. Otherwise, we want to somehow manipulate the elements so the binary search ends up checking $$$idx_x$$$.

Suppose the binary search is currently working on some range $$$[a, b]$$$. Let $$$m = \lfloor\frac{a + b}{2}\rfloor$$$. If $$$p_m = x$$$, we are done. Otherwise, consider the following cases:

• $$$p_m \lt x$$$ and $$$m \lt idx_x$$$: the binary search will continue on $$$[m+1, b]$$$, and since $$$idx_x$$$ belongs in that range, we simply let it continue. We must not swap this value.
• $$$p_m \lt x$$$ and $$$m \gt idx_x$$$: the binary search will continue on $$$[m+1, b]$$$, but $$$idx_x$$$ does not belong in that range. To fix this, we must replace $$$p_m$$$ with a value that is greater than $$$x$$$, in which case the search will continue on $$$[a, m-1]$$$.
• $$$p_m \gt x$$$ and $$$m \lt idx_x$$$: the binary search will continue on $$$[a, m-1]$$$, but $$$idx_x$$$ does not belong in that range. To fix this, we must replace $$$p_m$$$ with a value that is less than $$$x$$$, in which case the search will continue on $$$[m+1, b]$$$.
• $$$p_m \gt x$$$ and $$$m \gt idx_x$$$: the binary search will continue on $$$[a, m-1]$$$, and since $$$idx_x$$$ belongs in that range, we simply let it continue. We must not swap this value.

Keep doing this process until $$$p_m = x$$$. Suppose that the amount of integers less than $$$x$$$ needed are $$$s$$$, and the amount of integers greater than $$$x$$$ needed are $$$b$$$. In addition, let the values smaller than $$$x$$$ that we can't swap (because they already lead to the wanted direction) be denoted by $$$ss$$$ and those bigger as $$$bb$$$. There are $$$n - x$$$ greater values available in $$$p$$$, and $$$x-1$$$ smaller values available. Therefore, if $$$b \gt n - x - bb$$$ or $$$s \gt x - 1 - ss$$$, the answer is $$$-1$$$.

If the answer is not $$$-1$$$, we swap as many values as possible from $$$b$$$ and $$$s$$$ (which will be $$$\min{(b, s)} * 2$$$) and those that are still left after that (which will be $$$(\max{(b, s)} - \min{(b, s)}) * 2)$$$. The final answer is $$$(\max{(b, s)} - \min{(b, s)}) * 2 + \min{(b, s)} * 2$$$.

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
void solve() {
    int n, q; cin >> n >> q;
    int arr[n+1];
    vector<int> idx(n+1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        idx[arr[i]] = i;
    }
    while (q--) {
        int l, r, k; cin >> l >> r >> k;
        if (idx[k] > r || idx[k] < l) {
            cout << -1 << " ";
            continue;
        }
        int big = n - k, small = k - 1;
        int needBig = 0, needSmall = 0;
        int bigAv = n - k, smallAv = k - 1;
        int lo = l, hi = r;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (arr[mid] == k) break;
            if (mid < idx[k]) { // i want to go right
                if (k < arr[mid]) {
                    needSmall++;
                }
                else smallAv--;
                small--;
                lo = mid+1;
            }
            else { // i want to go left
                if (k > arr[mid]) { 
                    needBig++;
                }
                else bigAv--;
                big--;
                hi = mid-1;
            }
        }
        if (big < 0 || small < 0) {
            cout << -1 << " ";
            continue;
        }
        int ans = 2 * min(needBig, needSmall);
        int diff = abs(needBig - needSmall);
        if (needBig > needSmall) {
            if (bigAv < diff) cout << -1 << " ";
            else cout << ans + 2 * diff << " ";
        }
        else {
            if (smallAv < diff) cout << -1 << " ";
            else cout << ans + 2 * diff << " ";
        }
    }
}
 
signed main() {
    int t; cin >> t;
    while (t--){
      solve();
      cout << "\n";
    }
    return 0;
}

• Amazing
• Good
• Average
• Bad
• Didn't Solve

Each column can be broken down to $$$3$$$ components:

• If $$$a_i = 0$$$, the top-most component will contain $$$i-1$$$ zeros, the second component a single one, and the third component $$$n-i$$$ zeros.
• If $$$a_i = 1$$$, the top-most component will contain $$$i-1$$$ ones, the second component a single zero, and the third component $$$n-i$$$ ones.

The easiest way to visualize is with DSU. For each column, create $$$3$$$ components, and for each component implicitly store the number of $$$0$$$s in it. Now, we will try to merge all adjacent components that both consist of zeros. Consider the following transitions, for every $$$1 \lt i \le n$$$:

• If $$$a_i = 0$$$ and $$$a_{i-1} = 0$$$, then the top-most component of column $$$i-1$$$ will be merged with the top-most component of column $$$i$$$. The same goes for the two bottom-most components.
• If $$$a_i = 0$$$ and $$$a_{i-1} = 1$$$, then the top-most component of column $$$i$$$ will be merged with the top-most component of column $$$i-1$$$.
• If $$$a_i = 1$$$ and $$$a_{i-1} = 0$$$, then the bottom-most component of column $$$i$$$ will be merged with the bottom-most component of column $$$i-1$$$.
• If $$$a_i = 1$$$ and $$$a_{i-1} = 1$$$, we merge nothing.

After we finish the merging, we just take the component with the maximum number of zeros, which will be the answer to this problem. Note that you do not actually have to use DSU; we only care about the sizes and not the representatives, so we can also use simple prefix sums.

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
void solve() {
    int n; cin >> n;
    string s; cin >> s;
    s = " " + s;
    vector<int> top(n+1, 0), bot(n+1, 0);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == '1') {
            top[i] = bot[i-1] + 1;
        }
        else {
            top[i] = top[i-1] + (i - 1);
            bot[i] = bot[i-1] + (n - i);
        }
        ans = max(ans, max(top[i], bot[i]));
    }
    cout << ans << "\n";
}
 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }
 
struct DSU{
    vector<int> p, sz;
    vector<ll> score;
    
    DSU(int n){
        p.assign(n, 0);
        sz.assign(n, 1);
        score.assign(n, 0);
        
        for (int i = 0; i < n; i++) p[i] = i;
    }
    
    int find(int u){
        if (p[u] == u) return u;
        p[u] = find(p[u]);
        return p[u];
    }
    
    void unite(int u, int v){
        u = find(u);
        v = find(v);
        if (u == v) return;
        
        if (sz[u] < sz[v]) swap(u, v);
        p[v] = u;
        sz[u] += sz[v];
        score[u] += score[v];
    }
    
    bool same(int u, int v){
        return find(u) == find(v);
    }
    
    int size(int u){
        u = find(u);
        return sz[u];
    }
};
 
void solve(){
    int n;
    cin >> n;
 
    string s;
    cin >> s;
    
    DSU dsu(2 * n);
    vector<array<int, 2>> prev;
    for (int i = 0; i < n; i++){
        if (s[i] == '1'){
            dsu.score[2 * i] = 1;
            dsu.unite(2 * i, 2 * i + 1);
            
            for (int j = 0; j < prev.size(); j++){
                int l = prev[j][0];
                int r = prev[j][1];
                if (i >= l && i <= r)
                    dsu.unite(2 * i, 2 * (i - 1) + j);
            }
            prev = {{i, i}};
            continue;
        }
 
        vector<array<int, 2>> nxt = {{0, i - 1}, {i + 1, n - 1}};
        for (int j = 0; j < nxt.size(); j++){
            auto [l, r] = nxt[j];
            dsu.score[2 * i + j] = r - l + 1;
        }
 
        for (int j = 0; j < prev.size(); j++){
            for (int k = 0; k < nxt.size(); k++){
                auto [l1, r1] = prev[j];
                auto [l2, r2] = nxt[k];
 
                if (l2 > r1 || r2 < l1)
                    continue;
 
                dsu.unite(2 * i + k, 2 * (i - 1) + j);
            }
        }
        prev = nxt;
    }
 
    ll ans = 0;
    for (int i = 0; i < 2 * n; i++)
        ans = max(ans, dsu.score[i]);
    cout << ans << "\n";
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

• Amazing
• Good
• Average
• Bad
• Didn't Solve

For some node $$$u$$$, let $$$v_u$$$ be its value and $$$s_u$$$ be the sum of the values of all nodes on the simple path from the root of the tree to node $$$u$$$ ($$$s_u$$$ will also be referenced as "the sum of node $$$u$$$" for the purposes of this solution). Also, let $$$p_u$$$ be the parent of node $$$u$$$ (if $$$u$$$ is not the root).

Suppose that we know which node is the root of the tree. Then, we can make $$$n$$$ queries to find $$$s_1, s_2, ..., s_n$$$, which is sufficient to figure out $$$v_1, v_2, ..., v_n$$$: it holds that $$$s_u = s_{p_u} + v_u$$$, therefore $$$v_u = s_u - s_{p_u}$$$.

Then, we have $$$200$$$ queries left to find the actual root of the tree. Consider some node $$$u$$$, and all of its neighbor nodes $$$c_1, c_2, ..., c_k$$$.

Observation 1: Toggling the value of node $$$u$$$ will change the sum of every adjacent node to $$$u$$$ that is not the parent.

Observation 2: We can find the parent of node $$$u$$$ within $$$3\log k$$$ queries. Consider doing binary search to find which node does not change its sum when toggling the value of $$$u$$$. In order to check if the prefix $$$c_1, c_2, ..., c_m$$$ includes the parent of $$$u$$$, we do the following: query for $$$s1 = s_{c_1} + s_{c_2} + ... + s_{c_m}$$$, toggle the value of $$$u$$$, and query for $$$s2 = s_{c_1}' + s_{c_2}' + ... + s_{c_m}'$$$ again. Let $$$D = |s1 - s2|$$$. From Observation 1, if every node among $$$c_1, c_2, ..., c_m$$$ changed its value, then $$$D = 2m$$$, so we know that the parent does not belong in that prefix. Otherwise, there is a node that did not change its sum, so we can continue our binary search on that prefix. This takes $$$3$$$ queries performed $$$\log k$$$ times. Note that if we never find the parent, it must mean that $$$u$$$ is the root of the tree.

Since the tree is a star, if we find the parent of node $$$1$$$, we will find the root. If there does not exist a parent, then $$$1$$$ is the root. The problem has been solved in $$$n + 3 \log(n)$$$ queries, which comfortably fits the query limit.

There are a lot of other (better) solutions for this version (for example, this solution), but this solution helps best for coming up with the idea for G2.

#include <bits/stdc++.h>
using i64 = long long;
 
void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n+1), son(n-1);
    for (int i = 1; i < n; ++i) {
        int u, v;
        std::cin >> u >> v;
        son[i-1] = i + 1;
    }
    int Q = 0;
    auto ask = [&](int op, const std::vector<int> &v) {
        if (++Q > n + 200) {
            assert(false);
        }
        std::cout << "? " << op;
        if (op == 1) {
            std::cout << ' ' << v.size();
            for (auto u: v) std::cout << ' ' << u;
            std::cout << std::endl;
            int res = 0;
            std::cin >> res;
            return res;
        } else {
            std::cout << ' ' << v[0] << std::endl;
            return 0;
        }
    };
    int rt = 0;
    int bef = ask(1, son);
    ask(2, std::vector<int>{1});
    int af = ask(1, son);
    if (std::abs(bef - af) == 2 * son.size()) {
        rt = 1;
    } else {
        int l = 0, r = son.size() - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            std::vector<int> query(son.begin() + l, son.begin() + mid + 1);
            int bef = ask(1, query);
            ask(2, std::vector<int>{1});
            int af = ask(1, query);
            if (std::abs(bef - af) != 2 * (mid - l + 1)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        rt = son[l];
    }
    for (int i = 1; i <= n; ++i) {
        a[i] = ask(1, std::vector<int>{i});
    }
    for (int i = 2; i <= n; ++i) {
        if (rt != i) {
            a[i] -= a[1];
        }
    }
    if (rt > 1) a[1] -= a[rt];
    std::cout << '!';
    for (int i = 1; i <= n; ++i) {
        std::cout << ' ' << a[i];
    }
    std::cout << std::endl;
}
 
int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    std::cin >> T;
    while (T--) solve();
    return 0;
}

• Amazing
• Good
• Average
• Bad
• Didn't Solve

Read the solution to the Easy Version first.

Obviously, if we know the parent of some node, we know which nodes are under that node's subtree, so we never have to consider them as candidates for the root of the tree. Let's use this to choose nodes in a way such that each time we eliminate as many candidates as possible, even in the worst case.

Specifically, consider querying for the centroid of the tree (a centroid of a tree is a node that if it is deleted, every connected component left has size no more than half of the original tree). When querying for the centroid, there are two cases: either it is the root of the tree, in which case we are finished, or we find its parent, which eliminates at least half of the current candidates. Then, we delete all nodes that could not possibly be the root, and query for the new centroid.

Since the candidates get halved each time, we repeat the above process no more than $$$\log n$$$ times. In the absolute worst case (which is not realistic), we make $$$3\log (n) + 3\log (\frac{n}{2}) + 3\log (\frac{n}{4}) + ... + 3$$$ queries. For $$$n = 1000$$$, this is about $$$165$$$ queries. I do want to stress that this case is impossible; the $$$200$$$ queries are pretty loose but I want to allow a lot of different solutions (there are some even better ones than the one I described here, feel free to describe better solutions in the comments).

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
vector<vector<int>> tree, cd;
vector<int> sub, val;
vector<bool> del;
int n, cdRoot = -1;
 
int ask(vector<int> a) {
    int k = a.size();
    cout << "? 1 " << k << " ";
    for (auto x: a) {
        cout << x << " ";
    }
    cout << endl;
    int ans; cin >> ans;
    return ans;
}
 
void toggle(int u) {
    cout << "? 2 " << u << endl;
}
 
void answer(vector<int> ans) {
    cout << "! ";
    for (int i = 1; i <= n; i++) cout << ans[i] << " ";
    cout << endl;
}
 
void calc_sums(int node, int par = 0) {
    sub[node] = 0;
    if (del[node]) return;
    for (auto next: tree[node]) {
        if (next == par) continue;
        calc_sums(next, node);
        sub[node] += sub[next];
    }
    sub[node]++;
}
 
int find_centroid(int node, int sz, int par = 0) {
    for (auto next: tree[node]) {
        if (next == par || del[next]) continue;
        if (sub[next] * 2 >= sz) return find_centroid(next, sz, node);
    }
    return node;
}
 
void build(int node, int prev) {
    cd[prev].push_back(node);
    del[node] = true;
    for (auto next: tree[node]) {
        if (del[next]) continue;
        calc_sums(next, node);
        int cent = find_centroid(next, sub[next], node);
        build(cent, node);
    }
}
 
bool inspect(vector<int> a, int tog) {
    int b4 = ask(a);
    toggle(tog);
    int aft = ask(a);
    int k = a.size();
    int must = b4;
    if (aft < b4) {
        must -= 2 * k;
    }
    else must += 2 * k;
    if (aft != must) return true;
    else return false;
}
 
int find_sus(vector<int> a, int tog) {
    int k = a.size();
    int lo = 0, hi = k-1;
    int ans = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        vector<int> qr;
        for (int j = 0; j <= mid; j++) {
            qr.push_back(a[j]);
        }
        if (inspect(qr, tog)) {
            ans = mid;
            hi = mid-1;
        }
        else lo = mid+1;
    }
    return ans; 
}
 
int find_root(int node, int par = 0) {
    if (cd[node].empty()) return node;
    vector<int> ch;
    for (auto next: cd[node]) {
        if (next == par) continue;
        ch.push_back(next);
    }
    int sus = find_sus(ch, node);
    if (sus == -1) return node;
    return find_root(ch[sus], node);
}
 
void find_vals(int node, int par = 0, int above = 0) {
    val[node] -= above;
    above += val[node];
    for (auto next: tree[node]) {
        if (next != par) {
            find_vals(next, node, above);
        }
    }
}
 
void solve() {
    cin >> n;
    cd.assign(n+1, {});
    tree.assign(n+1, {});
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }    
    del.assign(n+1, false);
    sub.assign(n+1, 0);
    calc_sums(1);
    cdRoot = find_centroid(1, n);
    build(cdRoot, 0);
    int root = find_root(cdRoot);
    val.resize(n+1);
    for (int i = 1; i <= n; i++) {
        val[i] = ask({i});
    }
    find_vals(root);
    answer(val);
}
 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Amazing
• Good
• Average
• Bad
• Didn't Solve

What happens when adding an edge between two nodes with distance of $$$k$$$ (amount of edges in the simple path from one node to another is $$$k$$$)?

Suppose that the amount of edges in the simple path from $$$u$$$ to $$$v$$$ is $$$k$$$. Adding a new edge $$$(u, v)$$$ will create a new cycle of $$$k$$$ nodes (with $$$k+1$$$ edges). Therefore, in order to create a cycle of size at least $$$3$$$, it is enough to find any two nodes that are not adjacent and connect them.

Due to the small constraints, it is enough to try all possible pairs of nodes and check if they're neighbors or not.

#include <bits/stdc++.h>
using namespace std;
 
vector<set<int>> tree;
 
void solve() {
    int n; cin >> n;
    tree.resize(n+1);
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        tree[u].insert(v);
        tree[v].insert(u);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;
            if (tree[i].find(j) == tree[i].end()) {
                cout << i << " " << j << "\n";
                return;
            }
        }
    }
}
 
int main() {
    solve();
    return 0;
}

#include<bits/stdc++.h>
#define pi 3.14159265358979323846
#define eb emplace_back
#define ll long long
#define w(t) while(t--)
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
//give sin(),cos() radian, and asin(),acos() gives you radian
bool ch[110][110];
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int n,a,b;
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>a>>b;
		ch[a][b]=1;
		ch[b][a]=1;
	}
	for(int i=1;i<n;i++){
		for(int j=i+1;j<=n;j++){
			if(!ch[i][j]){
				cout<<i<<' '<<j;
				return 0;
			}
		}
	}
	return 0;
}

Can you solve this problem in $$$O(n)$$$ and without any tree traversal algorithms?

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

If $$$d$$$ is the root of the tree, what is Spyrosaliv's best strategy? What is Cow the Cow's?

Spyrosaliv has a greedy strategy.

Spyrosaliv will keep decreasing the depth of the node he is on, until he reaches the root. How can Cow the Cow prevent this?

Spyrosaliv plays first, therefore if $$$s$$$ is adjacent to $$$d$$$ he wins.

Otherwise, it is impossible for him to win.

#include <bits/stdc++.h>
using namespace std;
 
const int MN = 2e5+1;
vector<vector<int>> tree(MN);
 
void solve() {
    int n, s, d; cin >> n >> s >> d;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    for (auto next: tree[s]) {
        if (next == d) {
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

Suppose there are $$$q$$$ queries. In each query, you are asked about the answer for different values of $$$s$$$ and $$$d$$$. How can you solve this problem in $$$O(n + q)$$$?

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

What is a property of a node $$$u$$$ that makes it impossible to win starting from that node?

Notice that it is always possible to win starting from the root of any tree. Why so?

Think of the way a DFS traversal visits the nodes of a tree.

For each node, if it is the root or its parent has more than $$$1$$$ child, then you can win starting from that node. Otherwise, you cannot.

#include <bits/stdc++.h>
using namespace std;

const int MN = 2e5+1;

void solve() {
    int n; cin >> n;
    vector<int> cnt(n+1, 0), par(n+1);
    for (int i = 2; i <= n; i++) {
        int p; cin >> p;
        cnt[p]++;
        par[i] = p;
    }
    cout << 1;
    for (int i = 2; i <= n; i++) {
        cout << (cnt[par[i]] >= 2);
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

Suppose that the $$$i$$$-$$$th$$$ node has been assigned with a value $$$c_i$$$. You need $$$1$$$ second to paint a node. Painting node $$$u$$$ at the $$$j$$$-$$$th$$$ second costs $$$j \cdot c_u$$$ coins. What is the minimum amount of coins needed to paint the whole tree (if possible to paint it)?

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

We don't care about which edge has been assigned to what weight.

We can try creating the best path on the diameter of the tree.

We can swap any two weights as many times as we'd like, so we don't care about which edge has been assigned to what weight.

Let $$$pos$$$ denote the array of positive weights and $$$neg$$$ the array of negative weights, both sorted in descending order. Also let $$$p$$$ and $$$n$$$ denote the size of $$$pos$$$ and $$$neg$$$ respectively.

Notice that the optimal strategy is to first pick the edge with the maximum weight, then the edge with the maximum negative weight, then the edge with the second maximum weight, and so on. More formally, let $$$s_i$$$ be the best path of $$$i$$$ edges, for all $$$1 \le i \le 2*\min(p, n)$$$. Then, $$$s_i = \sum_{j=1}^{j= \lceil{\frac{i}{2}}\rceil} pos_j + \sum_{j=1}^{j= \lfloor{\frac{i}{2}}\rfloor} neg_j$$$.

Notice that there is one last restriciton: since we are placing the weights on edges of the tree, we cannot make a best path that needs more edges than the diameter of the tree.

Let $$$d$$$ be the amount of edges in the diameter of the tree. The answer will be $$$\max\limits_{1 \le i \le \min(d, 2*p)} s_i$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
const int MN = 2e5+1;
vector<vector<int>> tree(MN);
int n;
int diameter = 0, firstEnd = 0;
 
void dfs(int node, int par = 0, int d = 0) {
    if (d > diameter) {
        diameter = d;
        firstEnd = node;
    }
    for (auto next: tree[node]) {
        if (next != par) dfs(next, node, d+1);
    }
}
 
void find_diameter() {
    dfs(1);
    dfs(firstEnd);
}
 
void solve() {
    cin >> n;
    vector<int> pos, neg;
    for (int i = 1; i < n; i++) {
        int u, v, w; cin >> u >> v >> w;
        tree[u].push_back(v);
        tree[v].push_back(u);
        if (w > 0) pos.push_back(w);
        else neg.push_back(w);
    }
    sort(pos.rbegin(), pos.rend());
    sort(neg.rbegin(), neg.rend());
    if (pos.size() == 0) {
        cout << neg[0] << "\n";
        return;
    }
    vector<ll> fin;
    int pSz = pos.size(), nSz = neg.size();
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            if (i / 2 == pSz) {
                fin.pop_back();
                break;
            }
            else fin.push_back(pos[i/2]);
        }
        else {
            if (i / 2 == nSz) break;
            else fin.push_back(neg[i/2]);
        }
    }
    int sz = fin.size();
    for (int i = 1; i < sz; i++) fin[i] += fin[i-1];
    find_diameter();
    ll ans = 0;
    for (int i = 0; i < min(sz, diameter); i++) {
        ans = max(ans, (ll)fin[i]);
    }
    cout << ans << "\n";
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

What if you could perform at most $$$k$$$ operations?

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

Two nodes $$$a$$$ and $$$b$$$ are considered similiar if and only if there exists another node $$$c$$$ such that it is an ancestor of both $$$a$$$ and $$$b$$$ and $$$dist(a, c) \equiv dist(b, c) \equiv 0 \pmod{k}$$$. Then, $$$c$$$ is going to be similiar to $$$a$$$, as $$$dist(a, c) \equiv dist(c, c) \equiv 0 \pmod{k}$$$, since $$$c$$$ is an ancestor of itself. For the same reason, $$$b$$$ is similiar to $$$c$$$. Furthermore, a node is similiar to all of its descendants with distance divisible by $$$k$$$, so all those nodes are similiar to each other.

For those reasons, the similarity is transmissive: if a node $$$u$$$ is similiar to a node $$$v$$$, and node $$$v$$$ is similiar to a node $$$x$$$, then node $$$u$$$ is similiar to node $$$x$$$. Therefore, all similiar nodes form non-intersecting components.

This observation leads us to think of the problem from a different prespective. Instead of going over all possible pairs $$$a$$$ and $$$b$$$, we can iterate over all possible nodes as $$$c$$$ (the ancestor of $$$a$$$ and $$$b$$$). Then, we are going to place all descendants with distance exactly $$$k$$$ inside the same component as node $$$c$$$.

The final part of the solution can be done in two ways, as listed below.

This solution uses DP on tree.

Let $$$dp_u$$$ be the number of nodes under $$$u$$$'s subtree with distance from $$$u$$$ divisible by $$$k$$$. If we do a dfs starting from the leaves, and the $$$k$$$-$$$th$$$ ancestor of a node $$$v$$$ is $$$u$$$, the transition will be $$$dp_u := dp_v + dp_u$$$. Initially $$$dp_u = 1$$$ for all $$$n$$$ nodes (since the distance of a node from itself is $$$0$$$, which is divisible by $$$k$$$).

The answer will be the sum of $$$\frac{dp_u \cdot (dp_u - 1)}{2}$$$ for all nodes $$$u$$$ with depth up to $$$k$$$.

This solution uses Disjoint Set Union (DSU).

Let the $$$k$$$-$$$th$$$ ancestor of a node $$$u$$$ be $$$a_u$$$. Then, we will use DSU to merge nodes $$$u$$$ and $$$a_u$$$ for every node with depth of at least $$$k + 1$$$. Let the sizes of the final components be $$$s_1, s_2, ..., s_l$$$, where $$$l$$$ is the amount of the final components.

The answer will be $$$\sum_{i = 1}^{i = l} \frac{s_i \cdot (s_i - 1)}{2}$$$.

We do not need to use binary lifting or anything advanced to get the $$$k$$$-$$$th$$$ ancestor of each node.

A quicker approach can be implemented instead.

In the DFS, let your current position be $$$u$$$. If depth of $$$u$$$ is $$$k + 1$$$, then its $$$k$$$-$$$th$$$ ancestor is node $$$1$$$. Otherwise, if the depth is greater than $$$k + 1$$$, its $$$k$$$-$$$th$$$ ancestor is the most recently visited child of the $$$k$$$-$$$th$$$ ancestor of the parent of node $$$u$$$. Check implementations for more details.

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
const int MN = 2e5+1;
 
vector<vector<int>> tree(MN);
vector<int> up(MN); // store k-th ancestor for all nodes
vector<int> mainChild(MN), dp(MN, 1);
int n, k, ans = 0;
 
void dfs1(int node, int par, int dis) { // fill up array
    if (dis == k) {
        up[node] = 1;
    }
    else if (dis > k) {
        up[node] = mainChild[up[par]];
    }
    else up[node] = -1;
    for (auto next: tree[node]) {
        if (next != par) {
            mainChild[node] = next;
            dfs1(next, node, dis+1);
        }
    }
    if (up[node] != -1) dp[up[node]] += dp[node];
    if (dis < k) ans += dp[node]*(dp[node] - 1)/2;
}
 
void solve() {
    cin >> n >> k;
    for (int i = 2; i <= n; i++) {
        int p; cin >> p;
        tree[p].push_back(i);
    }
    dfs1(1, 0, 0);
    cout << ans << "\n";
}
 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("file.in", "r", stdin)
    //freopen("file.out", "w", stdout);
    int t = 1;
    while (t--) solve();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
const int MN = 2e5+1;

vector<vector<int>> tree(MN);
vector<int> up(MN); // store k-th ancestor for all nodes
vector<int> mainChild(MN);
int n, k, ans = 0;

int par[MN], sz[MN];
 
int find(int a) {
    if (a == par[a]) return a;
    return par[a] = find(par[a]);
}

void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    if(sz[a] > sz[b]) swap(a, b);
    par[a] = b;
    sz[b] += sz[a];
}

void dfs1(int node, int par, int dis) { // fill up array
    if (dis == k) {
        up[node] = 1;
    }
    else if (dis > k) {
        up[node] = mainChild[up[par]];
    }
    else up[node] = -1;
    for (auto next: tree[node]) {
        if (next != par) {
            mainChild[node] = next;
            dfs1(next, node, dis+1);
        }
    }
    if (up[node] != -1) {
        merge(node, up[node]);
    }
}
 
void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        par[i] = i;
        sz[i] = 1;
    }
    for (int i = 2; i <= n; i++) {
        int p; cin >> p;
        tree[p].push_back(i);
    }
    dfs1(1, 0, 0);
    vector<bool> added(n+1, false);
    for (int i = 1; i <= n; i++) {
        int rep = find(i);
        if (!added[rep]) {
            added[rep] = true;
            ans += sz[rep] * (sz[rep] - 1) / 2;
        }
    }
    cout << ans << "\n";
}
 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("file.in", "r", stdin)
    //freopen("file.out", "w", stdout);
    int t = 1;
    while (t--) solve();
    return 0;
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

We need to count the number of unordered pairs of nodes $$$(u, v)$$$ such that $$$(d_v + d_u)^2 = (d_v - d_u)^2 = dis(u, v)$$$ holds.

Solving the first equality:

Therefore, $$$d_u = 0$$$ or $$$d_v = 0$$$ should hold.

WLOG, assume $$$d_v = 0$$$. Then, solving the second equality:

Let $$$D = 1 - 8d_{lca(u, v)} + 4val_{lca(u, v)}$$$. By the Quadratic Formula, $$$d_u = \frac{1 \pm \sqrt{D}}{2}$$$, if $$$D \gt 0$$$ and $$$D$$$ an odd perfect square.

This allows us to count the number of pairs under a node's subtree if we treat that node as $$$lca(u, v)$$$. The actual counting can be done with Small-To-Large Merging, by keeping a frequency map for each node.

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
const int MN = 2e5+5;
const int MAXV = 1e8;
vector<vector<int>> tree(MN);
vector<int> val(MN), match(MN, 0);
vector<map<int, int>> subVals(MN);
int ans = 0, n;
 
void dfs(int node, int d = 0) {
    d += val[node];
    subVals[node][d]++;
    int D = 1 - 8 * d + 4 * val[node];
    int sol1 = MAXV+5, sol2 = MAXV+5;
    if (D > 0 && D % 2 == 1) {
        int s = sqrt(D);
        if (s * s == D) {
            sol1 = (1 + s)/2; // two different roots, D != 0
            sol2 = (1 - s)/2;
        }
    }
    for (auto next: tree[node]) {
        dfs(next, d);
        if (subVals[next].size() > subVals[node].size()) swap(subVals[next], subVals[node]); // small to large
        for (auto [a, b]: subVals[next]) {
            if (a == 0) {
                ans += b * subVals[node][sol1]; // sol1 = sol2 iff sol1 = sol2 = 1e8+5, removed
                ans += b * subVals[node][sol2];
            }
            else if (a == sol1 || a == sol2) {
                ans += b * subVals[node][0];
            }
        }
        for (auto [a, b]: subVals[next]) {
            if (abs(a) > MAXV) continue;
            subVals[node][a] += b;
        }
    }
}
 
void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> val[i];
    for (int i = 2; i <= n; i++) {
        int p; cin >> p;
        tree[p].push_back(i);
    }
    dfs(1);
    cout << ans << "\n";
}
 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n;
ll  ans;
ll  val[N],fa[N],d[N],numS[N];
vector<int> G[N];
set<pair<ll,ll> > S[N];
 
/*
 * stuff you should look for
 * [Before Submission]
 * array bounds, initialization, int overflow, special cases (like n=1), typo
 * [Still WA]
 * check typo carefully
 * casework mistake
 * special bug
 * stress test
 */
 
void init()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>val[i];
    for(int i=2;i<=n;i++)
    {
        cin>>fa[i];
        G[i].push_back(fa[i]);
        G[fa[i]].push_back(i);
    }
}
 
void uni_set(int x,int y)
{
    if(x==y) return ;
    while(!S[y].empty())
    {
        pair<ll,ll> pr=*S[y].begin();
        set<pair<ll,ll> >::iterator it=S[x].lower_bound(make_pair(pr.first,0));
        S[y].erase(pr);
        if(it==S[x].end()||it->first!=pr.first) S[x].insert(pr);
        else
        {
            pr.second+=it->second;
            S[x].erase(it);
            S[x].insert(pr);
        }
    }
}
 
ll count_occ(ll x,ll v)
{
    set<pair<ll,ll> >::iterator it=S[x].lower_bound(make_pair(v,0));
    if(it==S[x].end()||it->first!=v) return 0;
    else return it->second;
}
 
pair<ll,ll> solve_equation(ll C)
{
    //solve x^2-x-C=0
    ll delta=1+4*C,sd;
    if(delta<0) return make_pair(INF*INF,INF*INF);
    sd=(ll)sqrt(delta);
    if(sd*sd!=delta||(sd%2==0)) return make_pair(INF*INF,INF*INF);
    else return make_pair((1+sd)/2,(1-sd)/2);
}
 
void DFS(int x)
{
    //
    //printf("x=%d\n",x);
    //
    ll mxsz=0,mxnum;
    d[x]=val[x]+d[fa[x]];
    for(int i=0;i<G[x].size();i++)
    {
        int y=G[x][i];
        if(y==fa[x]) continue;
        DFS(y);
        if(S[numS[y]].size()>mxsz)
            mxsz=S[numS[y]].size(),mxnum=numS[y];
    }
    if(x!=1&&G[x].size()==1)
    {
        numS[x]=x;
        S[x].insert(make_pair(d[x],1));
        return ;
    }
    ll C=val[x]-2*d[x];
    pair<ll,ll> root=solve_equation(C);
    if(root.first!=INF*INF)
    {
        ll r[2]={root.first,root.second};
        ll c0=(d[x]==0);
        for(int i=0;i<G[x].size();i++)
        {
            int y=G[x][i];
            if(y==fa[x]) continue;
            c0+=count_occ(numS[y],0);
        }
        for(int i=0;i<2;i++)
        {
            ll tans=0;
            for(int j=0;j<G[x].size();j++)
            {
                int y=G[x][j];
                if(y==fa[x]) continue;
                tans+=count_occ(numS[y],r[i])*(c0-count_occ(numS[y],0));
            }
            if(d[x]==r[i])
                tans+=(c0-(d[x]==0));
            if(!r[i]) tans/=2;
            ans+=tans;
        }
    }
    numS[x]=mxnum;
    for(int i=0;i<G[x].size();i++)
    {
        int y=G[x][i];
        if(y==fa[x]) continue;
        if(numS[y]!=mxnum) uni_set(mxnum,numS[y]);
    }
    S[x].insert(make_pair(d[x],1));
    uni_set(mxnum,x);
}
 
void solve()
{
    DFS(1);
    cout<<ans<<'\n';
}
 
//-------------------------------------------------------
 
void gen_data()
{
    srand(time(NULL));
}
 
int bruteforce()
{
    return 0;
}
 
//-------------------------------------------------------
 
int main()
{
    fastio;
 
    T=1;
	//cin>>T;
	while(T--)
	{
		init();
		solve();
 
		/*
 
		//Stress Test
 
		gen_data();
		auto ans1=solve(),ans2=bruteforce();
		if(ans1==ans2) printf("OK!\n");
		else
		{
			//Output Data
 		}
 
		*/
	}
 
	return 0;
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

Before solving the actual problem, let's see an easier version where no nodes are ever blocked.

First, let's see what is the optimal strategy for the cows. Since every cow has a positive value and their priority is to maximize the score of the game, they will all meet at the same node. In order to minimize the time of the game, they will meet at the node that is the closest to every cow and that is an ancestor of all nodes with a cow.

Let the current game be represented by an integer $$$k$$$ — the number of cows, and $$$pos_1, pos_2, ..., pos_k$$$, where $$$pos_i$$$ is the node of the $$$i$$$-$$$th$$$ cow. Then, the node they will meet at is $$$u = lca(pos_1, pos_2, ..., pos_k)$$$. Let $$$dep_u$$$ be the depth of node $$$u$$$. Then it's easy to see that the time they will need to meet at that $$$u$$$ is going to be $$$\max\limits_{1 \le i \le k} (dep_{pos_i}) - dep_u$$$.

Now, we just need to efficiently calculate these values for each game. Notice that $$$lca(x, y, z) = lca(x, lca(y, z))$$$. Therefore, we can reverse the queries and answer them offline. Now, each query pretty much is asking to add a cow instead of removing one. That's easier to keep track of, since we can keep the sum of the values of the cows, the deepest node a cow is on, and their LCA for each query.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
const int MN = 2e5+5;
vector<vector<int>> tree(MN), up;
vector<int> val(MN), pos(MN), depth(MN, 0), par(MN), sz(MN);
vector<ll> tin(MN), tout(MN);
int n, k, t = 0, l;
ll ans = 0;
 
bool is_anc(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
 
int lca(int a, int b) {
    if (a == b) return a;
    if (depth[a] < depth[b]) swap(a, b);
    int curr = a;
    for (int i = l; i >= 0; i--) {
        if (!is_anc(up[curr][i], b)) curr = up[curr][i];
    }
    return up[curr][0];
}
 
void dfs1(int node, int p = 0, int d = 1) {
    depth[node] = d;
    tin[node] = t;
    t++;
    up[node][0] = p;
    for (int i = 1; i <= l; i++) {
        up[node][i] = up[up[node][i-1]][i-1];
    }
    for (auto next: tree[node]) {
        if (next != p) dfs1(next, node, d+1);
    }
    tout[node] = t;
    t++;
}
 
void solve() {
    cin >> n >> k;
    l = ceil(log2(n));
    up.assign(n+1, vector<int>(l+1, 0));
    tin[0] = 0;
    tout[0] = LLONG_MAX;
    ll ans = 0;
    vector<bool> hasCow(n+1, false);
    for (int i = 1; i <= k; i++) {
        cin >> pos[i];
        hasCow[pos[i]] = true;
    }
    for (int i = 1; i <= k; i++) {
        cin >> val[pos[i]];
        ans += val[pos[i]];
    }
    for (int i = 2; i <= n; i++) {
        int p; cin >> p;
        tree[p].push_back(i);
        tree[i].push_back(p);
    }
    int q; cin >> q;
    vector<pair<int, int>> queries(q);
    for (auto &[t, u]: queries) {
        cin >> t >> u;
        ans -= val[u];
        hasCow[u] = false;
    }
    dfs1(1);
    int lc = 0, deepest = 0;
    for (int i = 1; i <= n; i++) {
        if (hasCow[i]) {
            deepest = max(deepest, depth[i]);
            if (lc == 0) lc = i;
            else lc = lca(lc, i);
        }
    }
    vector<pair<ll, int>> answers;
    answers.push_back({ans, deepest - depth[lc]});
    reverse(queries.begin(), queries.end());
    for (auto [t, u]: queries) {
        ans += val[u];
        if (lc == 0) lc = u;
        else lc = lca(lc, u);
        deepest = max(deepest, depth[u]);
        answers.push_back({ans, deepest - depth[lc]});
    }
    reverse(answers.begin(), answers.end());
    for (auto [a, b]: answers) cout << a << " " << b << "\n";
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

Now we can solve the actual problem.

Notice that blocking a node splits the tree into multiple components. More specifically, by blocking a node, we split the whole game into multiple smaller games. Out of all the non-intersecting & smaller games, we will keep the one with the maximum final score. If there are many such games, we will keep the one with the minimum time needed to be finished. These two values will be the answer to each query.

But how do we handle multiple games for many queries efficiently? Let's use the idea of the Easy Version of this problem. That is, we will reverse the queries, as adding cows and "unblocking" nodes is easier to do than removing cows and blocking nodes. As mentioned before, we have multiple components, each representing a different game. For each such component, we need to maintain the same information as for the Easy Version: the deepest node with a cow, the LCA of all nodes with a cow and the total sum of the values of the cows.

To easily keep track of all components, we will use Disjoint Set-Union.

Merging two components is simple: the LCA of the new component will be the LCA of the LCAs of the two other components, the deepest node with a cow will be the deepest node with a cow from the two other components, and the total sum of values will be the sum of the values of the two components to be merged. In an identical way, we can add a cow to the tree.

To "unblock" a node, we will create a new component that initially consists only of this node. Then, we will iterate over all nodes that are not blocked and that are adjacent to this node and merge their components. Note that this is possible without going over the time limit, as each node can be "unblocked" at most once.

Finally, we will maintain the maximal possible score and the minimum time to achieve it and update these values accordingly for each new merge.

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
const int MN = 2e5+5;
vector<vector<int>> tree(MN), up;
vector<int> val(MN), pos(MN), depth(MN, 0), par(MN), sz(MN), compLCA(MN), score(MN), deepest(MN), tin(MN), tout(MN);
vector<bool> blocked(MN, false), hasCow(MN, false);
int n, k, ans = 0, minTime = 0, t = 0, l;
 
bool is_anc(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
 
int lca(int a, int b) {
    if (a == b) return a;
    if (depth[a] < depth[b]) swap(a, b);
    int curr = a;
    for (int i = l; i >= 0; i--) {
        if (!is_anc(up[curr][i], b)) curr = up[curr][i];
    }
    return up[curr][0];
}
 
int find(int node) {
    if (par[node] == node) return node;
    return par[node] = find(par[node]);
}
 
void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    if (sz[a] > sz[b]) swap(a, b);
    par[a] = b;
    sz[b] += sz[a];
    if (hasCow[a] && hasCow[b]) {
        int x = lca(compLCA[b], compLCA[a]);
        compLCA[b] = x;
    }
    else if (hasCow[a]) {
        compLCA[b] = compLCA[a];
        hasCow[b] = true;
    }
    score[b] = score[b] + score[a];
    deepest[b] = max(deepest[b], deepest[a]);
    if (score[b] == ans) {
        minTime = min(minTime, abs(depth[compLCA[b]] - deepest[b]));
    }
    else if (score[b] > ans) {
        ans = score[b];
        minTime = abs(depth[compLCA[b]] - deepest[b]);
    }
}
 
void dfs1(int node, int p = 0, int d = 1) {
    depth[node] = d;
    if (hasCow[node]) deepest[node] = d;
    if (hasCow[node]) compLCA[node] = node;
    tin[node] = t;
    t++;
    up[node][0] = p;
    for (int i = 1; i <= l; i++) {
        up[node][i] = up[up[node][i-1]][i-1];
    }
    for (auto next: tree[node]) {
        if (next != p) dfs1(next, node, d+1);
    }
    tout[node] = t;
    t++;
}
 
void dfs2(int node, int p = 0) {
    for (auto next: tree[node]) {
        if (next != p) {
            dfs2(next, node);
            if (!blocked[node] && !blocked[next]) merge(node, next);
        }
    }
}
 
void solve() {
    cin >> n >> k;
    l = ceil(log2(n));
    up.assign(n+1, vector<int>(l+1, 0));
    tin[0] = 0;
    tout[0] = LLONG_MAX;
    for (int i = 1; i <= n; i++) {
        par[i] = i;
        sz[i] = 1;
        compLCA[i] = i;
        score[i] = 0;
        deepest[i] = 0;
    }
    for (int i = 1; i <= k; i++) {
        cin >> pos[i];
        hasCow[pos[i]] = true;
    }
    for (int i = 1; i <= k; i++) {
        cin >> val[pos[i]];
        score[pos[i]] = val[pos[i]]; 
    }
    for (int i = 2; i <= n; i++) {
        int p; cin >> p;
        tree[p].push_back(i);
        tree[i].push_back(p);
    }
    int q; cin >> q;
    vector<pair<int, int>> queries(q);
    for (auto &[t, u]: queries) {
        cin >> t >> u;
        if (t == 1) {
            hasCow[u] = false;
            score[u] = 0;
        }
        else blocked[u] = true;
    }
    dfs1(1);
    dfs2(1);
    for (int i = 1; i <= n; i++) ans = max(ans, score[i]);
    if (q == 0) {
        cout << ans << " " << minTime << "\n";
        return;
    }
    vector<pair<int, int>> answers;
    answers.push_back({ans, minTime});
    reverse(queries.begin(), queries.end());
    for (auto [t, u]: queries) {
        if (t == 2) { // unblock u
            blocked[u] = false;
            for (auto x: tree[u]) {
                if (!blocked[x]) merge(x, u);
            }
        }
        else {
            int rep = find(u);
            int plusScore = val[u];
            if (!hasCow[rep]) {
                hasCow[rep] = true;
                score[rep] = plusScore;
                deepest[rep] = depth[u];
                compLCA[rep] = u;
            }
            else {
                score[rep] += plusScore;
                deepest[rep] = max(deepest[rep], depth[u]);
                compLCA[rep] = lca(compLCA[rep], u);
            }
            if (score[rep] == ans) {
                minTime = min(minTime, abs(depth[compLCA[rep]] - deepest[rep]));
            }
            if (score[rep] > ans) {
                ans = score[rep];
                minTime = abs(depth[compLCA[rep]] - deepest[rep]);
            }
        }
        answers.push_back({ans, minTime});
    }
    reverse(answers.begin(), answers.end());
    for (auto [a, b]: answers) cout << a << " " << b << "\n";
}
 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("file.in", "r", stdin)
    //freopen("file.out", "w", stdout);
    int t = 1;
    while (t--) solve();
    return 0;
}

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=200010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n,k,q;
ll  pos[N],val[N],cow[N],t[N],u[N];
 
/*
 * stuff you should look for
 * [Before Submission]
 * array bounds, initialization, int overflow, special cases (like n=1), typo
 * [Still WA]
 * check typo carefully
 * casework mistake
 * special bug
 * stress test
 */
 
struct state
{
   ll num,sum,tm;
 
   state() {}
 
   state(ll num,ll sum,ll tm):num(num),sum(sum),tm(tm) {}
 
   friend bool operator <(state x,state y)
   {
       if(x.sum!=y.sum) return x.sum>y.sum;
       else if(x.tm!=y.tm) return x.tm<y.tm;
       else return x.num<y.num;
   }
};
set<state> S;
 
//-------------------------------------------------
//涉及变量:n(点数),G(图),d[](节点深度),f[][](祖先ST表)
//注意: 节点编号为1-n
 
ll  rt=1;
ll  d[N];
ll  f[N][LOGN];
vector<int> G[N];
 
void DFS(int x,int pre)
{
	f[x][0]=pre;
	d[x]=d[pre]+1;
	for(int i=0;i<G[x].size();i++)
	{
		int y=G[x][i];
		if(y==pre) continue;
		DFS(y,x);
	}
}
 
void init_lca()	//算出d[],f[][]
{
	DFS(rt,0);
	for(int i=1;i<LOGN;i++)
		for(int j=1;j<=n;j++)
			f[j][i]=f[f[j][i-1]][i-1];
}
 
int lca(int x,int y)
{
    //
    if(x==0) return y;
    if(y==0) return x;
    //
	if(d[x]>d[y]) swap(x,y);
	for(int i=LOGN-1;i>=0;i--) if(d[f[y][i]]>=d[x]) y=f[y][i];
	if(x==y) return x;
	for(int i=LOGN-1;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}
 
//-------------------------------------------------
 
//-------------------------------------------------
//涉及变量:f[]
//注意:自行初始化
 
ll F[N],LCA[N],mxd[N],sum[N];
 
int find(int x)
{
	return x==F[x]?x:F[x]=find(F[x]);
}
 
void uni(int x,int y)
{
	int fx=find(x),fy=find(y);
	F[fx]=fy;
	if(fx==fy) return;
    S.erase(state(fx,sum[fx],mxd[fx]-d[LCA[fx]]));
    S.erase(state(fy,sum[fy],mxd[fy]-d[LCA[fy]]));
    LCA[fy]=lca(LCA[fx],LCA[fy]);
    mxd[fy]=max(mxd[fx],mxd[fy]);
    sum[fy]+=sum[fx];
    S.insert(state(fy,sum[fy],mxd[fy]-d[LCA[fy]]));
	//if(fx!=fy) sz[fy]+=sz[fx]; //!!!
}
//-------------------------------------------------
 
void init()
{
    cin>>n>>k;
    for(int i=1;i<=k;i++) cin>>pos[i];
    for(int i=1;i<=k;i++) cin>>val[i];
    for(int i=2;i<=n;i++)
    {
        int fa;
        cin>>fa;
        G[i].push_back(fa);
        G[fa].push_back(i);
    }
    cin>>q;
    for(int i=1;i<=q;i++)
        cin>>t[i]>>u[i];
    for(int i=1;i<=k;i++) cow[pos[i]]=i;
    init_lca();
    for(int i=1;i<=n;i++) F[i]=i;
}
 
void solve()
{
    vector<int>   removed(n+4),blocked(n+4);
    vector<state> ans;
    for(int i=1;i<=q;i++)
        if(t[i]==1) removed[u[i]]=1;
    for(int i=1;i<=q;i++)
        if(t[i]==2) blocked[u[i]]=1;
    for(int i=1;i<=k;i++)
    {
        if(removed[pos[i]]) continue;
        LCA[pos[i]]=pos[i];
        mxd[pos[i]]=d[pos[i]];
        sum[pos[i]]=val[i];
    }
    for(int i=1;i<=n;i++)
        S.insert(state(i,sum[i],0));
    /*
    cout<<"n="<<n<<'\n';
    cout<<"pos[3]="<<pos[3]<<'\n';
    cout<<"val[3]="<<val[3]<<'\n';
    cout<<"sum[5]="<<sum[5]<<'\n';
    cout<<"init  "<<S.begin()->sum<<' '<<S.begin()->tm<<'\n';
    while(!S.empty())
    {
        cout<<"fk  "<<S.begin()->sum<<' '<<S.begin()->tm<<'\n';
        S.erase(S.begin());
    }
 
    */
    for(int i=1;i<=n;i++)
    {
        if(blocked[i]) continue;
        for(int j=0;j<G[i].size();j++)
        {
            int y=G[i][j];
            if(!blocked[y]) uni(i,y);
        }
    }
    //cout<<S.begin()->sum<<' '<<S.begin()->tm<<'\n';
    ans.push_back(*S.begin());
    for(int i=q;i;i--)
    {
        if(t[i]==1)
        {
            int fx=find(u[i]);
            S.erase(state(fx,sum[fx],mxd[fx]-d[LCA[fx]]));
            LCA[fx]=lca(LCA[fx],u[i]);
            mxd[fx]=max(mxd[fx],d[u[i]]);
            sum[fx]+=val[cow[u[i]]];
            S.insert(state(fx,sum[fx],mxd[fx]-d[LCA[fx]]));
        }
        else
        {
            blocked[u[i]]=0;
            for(int j=0;j<G[u[i]].size();j++)
            {
                int y=G[u[i]][j];
                if(!blocked[y]) uni(u[i],y);
            }
        }
        //cout<<S.begin()->sum<<' '<<S.begin()->tm<<'\n';
        ans.push_back(*S.begin());
    }
    reverse(ans.begin(),ans.end());
    for(int i=0;i<q+1;i++)
        cout<<ans[i].sum<<' '<<ans[i].tm<<'\n';
}
 
//-------------------------------------------------------
 
void gen_data()
{
    srand(time(NULL));
}
 
int bruteforce()
{
    return 0;
}
 
//-------------------------------------------------------
 
int main()
{
    fastio;
 
    T=1;
	//cin>>T;
	while(T--)
	{
		init();
		solve();
 
		/*
 
		//Stress Test
 
		gen_data();
		auto ans1=solve(),ans2=bruteforce();
		if(ans1==ans2) printf("OK!\n");
		else
		{
			//Output Data
 		}
 
		*/
	}
 
	return 0;
}

Originally, there was going to be a HLD Hard Version to this problem (which we ended up removing, as we were worried that there would be too much implementation for this contest), where there is a third type of query:

"3. Add cow with value $$$v$$$ to node $$$u$$$ (there is no cow at node $$$u$$$ beforehand)".

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve: